# 堆操作 for JavaScript **Repository Path**: dawnice/dtheaps ## Basic Information - **Project Name**: 堆操作 for JavaScript - **Description**: 为JavaScript环境编写的堆操作实现,可以上浮下沉,以及建堆、排序、查看、弹出、插入、替换和Top K,支持Node.js。 - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2026-08-18 - **Last Updated**: 2026-08-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: Heap, 堆, 排序, JavaScript, 数据 ## README # DTheaps - JavaScript 堆操作工具库 一个轻量级、高性能的 JavaScript 堆操作库,支持大顶堆和小顶堆,适用于浏览器和 Node.js 环境。 ## ✨ 特性 - 🚀 **高性能**:优化的堆操作算法,时间复杂度优秀 - 🌐 **跨平台**:同时支持浏览器和 Node.js 环境 - 📦 **零依赖**:纯 JavaScript 实现,无任何第三方依赖 - 🎯 **完整功能**:支持建堆、排序、插入、删除、Top K 等常用操作 - 📚 **友好文档**:详细的 API 文档和使用示例 - 🎨 **可视化演示**:提供完整的 HTML 演示页面 ## 📦 安装 ### 浏览器环境 直接下载 `dtheaps.js` 文件并在 HTML 中引入: ```html ``` ### Node.js 环境 #### 方式一:CommonJS (推荐) ```javascript const dtheaps = require('./dtheaps.js'); ``` #### 方式二:ES6 模块 **选项 A:创建包装文件** 创建 `dtheaps-esm.mjs` 文件: ```javascript // dtheaps-esm.mjs import { fileURLToPath } from 'url'; import { dirname } from 'path'; const __filename = fileURLToPath(import.meta.url); const __dirname = dirname(__filename); // 使用动态导入来加载 CommonJS 模块 const dtheaps = await import(__dirname + '/dtheaps.js'); export default dtheaps.default || dtheaps; ``` 然后使用: ```javascript import dtheaps from './dtheaps-esm.mjs'; ``` **选项 B:直接使用 .mjs 文件** 将 `dtheaps.js` 重命名为 `dtheaps.mjs`,然后取消文件末尾 `export` 语句的注释。 ```javascript import dtheaps from './dtheaps.mjs'; ``` ## 🚀 快速开始 ### 浏览器环境 ```html ``` ### Node.js 环境 ```javascript const dtheaps = require('./dtheaps.js'); // 建大顶堆 const arr = [7, 4, 2, 3, 6, 1, 5, 8]; dtheaps.buildHeapMax(arr); console.log(arr); // [8, 7, 6, 4, 3, 1, 5, 2] // 堆排序 const sorted = dtheaps.heapSortAsc([7, 4, 2, 3, 6, 1, 5, 8]); console.log(sorted); // [1, 2, 3, 4, 5, 6, 7, 8] ``` ## 📚 API 文档 ### 建堆操作 #### `buildHeapMax(arr)` 构建大顶堆,父节点 >= 子节点,堆顶为最大值。 **参数:** - `arr` (Array): 待构建的数组 **返回值:** - 修改后的数组 **时间复杂度:** O(n) ```javascript const arr = [7, 4, 2, 3, 6, 1, 5, 8]; buildHeapMax(arr); console.log(arr); // [8, 7, 6, 4, 3, 1, 5, 2] ``` #### `buildHeapMin(arr)` 构建小顶堆,父节点 <= 子节点,堆顶为最小值。 **参数:** - `arr` (Array): 待构建的数组 **返回值:** - 修改后的数组 **时间复杂度:** O(n) ```javascript const arr = [7, 4, 2, 3, 6, 1, 5, 8]; buildHeapMin(arr); console.log(arr); // [1, 4, 2, 3, 6, 7, 5, 8] ``` #### `buildHeap(arr, type)` 通用建堆函数。 **参数:** - `arr` (Array): 待构建的数组 - `type` (String): 'max' 或 'min',默认为 'max' **时间复杂度:** O(n) ### 堆排序 #### `heapSortAsc(arr)` 升序排序(使用大顶堆)。 **参数:** - `arr` (Array): 待排序的数组 **返回值:** - 排序后的新数组 **时间复杂度:** O(n log n) ```javascript const sorted = heapSortAsc([7, 4, 2, 3, 6, 1, 5, 8]); console.log(sorted); // [1, 2, 3, 4, 5, 6, 7, 8] ``` #### `heapSortDesc(arr)` 降序排序(使用小顶堆)。 **参数:** - `arr` (Array): 待排序的数组 **返回值:** - 排序后的新数组 **时间复杂度:** O(n log n) ```javascript const sorted = heapSortDesc([7, 4, 2, 3, 6, 1, 5, 8]); console.log(sorted); // [8, 7, 6, 5, 4, 3, 2, 1] ``` ### 查看堆顶 #### `heapPeekMax(arr)` 查看大顶堆的最大值,不删除。 **参数:** - `arr` (Array): 已构建的大顶堆 **返回值:** - 堆顶元素(最大值) **时间复杂度:** O(1) ```javascript const heap = [8, 7, 6, 4, 3, 1, 5, 2]; const max = heapPeekMax(heap); console.log(max); // 8 ``` #### `heapPeekMin(arr)` 查看小顶堆的最小值,不删除。 **参数:** - `arr` (Array): 已构建的小顶堆 **返回值:** - 堆顶元素(最小值) **时间复杂度:** O(1) ### 弹出堆顶 #### `heapPopMax(arr)` 弹出并返回大顶堆的最大值。 **参数:** - `arr` (Array): 已构建的大顶堆 **返回值:** - 被弹出的最大值 **时间复杂度:** O(log n) ```javascript const heap = [8, 7, 6, 4, 3, 1, 5, 2]; const max = heapPopMax(heap); console.log(max); // 8 console.log(heap); // [7, 6, 5, 4, 3, 1, 2] ``` #### `heapPopMin(arr)` 弹出并返回小顶堆的最小值。 **参数:** - `arr` (Array): 已构建的小顶堆 **返回值:** - 被弹出的最小值 **时间复杂度:** O(log n) ### 插入元素 #### `heapPushMax(arr, value)` 向大顶堆插入元素。 **参数:** - `arr` (Array): 已构建的大顶堆 - `value` (Any): 要插入的值 **返回值:** - 堆的新大小 **时间复杂度:** O(log n) ```javascript const heap = [8, 7, 6, 4, 3, 1, 5, 2]; heapPushMax(heap, 10); console.log(heap); // [10, 8, 6, 4, 7, 1, 5, 2, 3] ``` #### `heapPushMin(arr, value)` 向小顶堆插入元素。 **参数:** - `arr` (Array): 已构建的小顶堆 - `value` (Any): 要插入的值 **返回值:** - 堆的新大小 **时间复杂度:** O(log n) ### 替换堆顶 #### `heapReplaceMax(arr, value)` 替换大顶堆的堆顶元素。 **参数:** - `arr` (Array): 已构建的大顶堆 - `value` (Any): 新的堆顶值 **返回值:** - 原堆顶元素 **时间复杂度:** O(log n) ```javascript const heap = [8, 7, 6, 4, 3, 1, 5, 2]; const oldMax = heapReplaceMax(heap, 10); console.log(oldMax); // 8 console.log(heap); // [10, 7, 6, 4, 3, 1, 5, 2] ``` #### `heapReplaceMin(arr, value)` 替换小顶堆的堆顶元素。 **参数:** - `arr` (Array): 已构建的小顶堆 - `value` (Any): 新的堆顶值 **返回值:** - 原堆顶元素 **时间复杂度:** O(log n) ### Top K 问题 #### `findMaxK(arr, k)` 找出数组中最大的 k 个元素。 **参数:** - `arr` (Array): 输入数组 - `k` (Number): 要找的元素个数 **返回值:** - 包含最大 k 个元素的数组 **时间复杂度:** O(n log k) ```javascript const arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]; const max3 = findMaxK(arr, 3); console.log(max3); // [30, 28, 20] 或其他最大的 3 个 ``` #### `findMinK(arr, k)` 找出数组中最小的 k 个元素。 **参数:** - `arr` (Array): 输入数组 - `k` (Number): 要找的元素个数 **返回值:** - 包含最小 k 个元素的数组 **时间复杂度:** O(n log k) ```javascript const arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]; const min4 = findMinK(arr, 4); console.log(min4); // [2, 6, 10, 12] 或其他最小的 4 个 ``` ### 其他高级函数 #### `heapSortWithSteps(arr, type)` 带步骤记录的堆排序,用于演示教学。 **参数:** - `arr` (Array): 待排序的数组 - `type` (String): 'max' 或 'min',默认为 'max' **返回值:** - 对象,包含排序结果和详细步骤 ```javascript const result = heapSortWithSteps([7, 4, 2, 3, 6, 1, 5, 8], 'max'); console.log(result.result); // 排序后的数组 console.log(result.steps); // 详细步骤数组 ``` #### 基础操作函数 - `siftDownMax(arr, i, heapSize)`: 大顶堆下浮操作 - `siftDownMin(arr, i, heapSize)`: 小顶堆下浮操作 - `siftDown(arr, i, heapSize, compare)`: 通用下浮操作 - `siftUpMax(arr, i)`: 大顶堆上浮操作 - `siftUpMin(arr, i)`: 小顶堆上浮操作 - `siftUp(arr, i, compare)`: 通用上浮操作 ## 🎯 应用场景 1. **优先队列**:任务调度、事件驱动系统、Dijkstra 最短路径算法 2. **Top K 问题**:排行榜、热门推荐、异常检测 3. **堆排序**:外部排序、内存受限环境下的排序 4. **窗口问题**:滑动窗口最大值/最小值 5. **合并有序链表**:归并排序的变种 ## 📖 完整示例 ### 浏览器示例 ```html ``` ### Node.js 示例 ```javascript const dtheaps = require('./dtheaps.js'); // 1. 建堆 const arr1 = [7, 4, 2, 3, 6, 1, 5, 8]; dtheaps.buildHeapMax(arr1); console.log("大顶堆:", arr1); // 2. 排序 const arr2 = [7, 4, 2, 3, 6, 1, 5, 8]; const sorted = dtheaps.heapSortAsc(arr2); console.log("升序排序:", sorted); // 3. Top K 问题 const arr3 = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]; const max3 = dtheaps.findMaxK(arr3, 3); console.log("最大的3个:", max3); // 4. 堆操作 const heap = [7, 4, 2, 3, 6, 1, 5, 8]; dtheaps.buildHeapMax(heap); console.log("堆顶:", dtheaps.heapPeekMax(heap)); // 8 const popped = dtheaps.heapPopMax(heap); console.log("弹出:", popped); // 8 console.log("剩余堆:", heap); // [7, 6, 5, 4, 3, 1, 2] dtheaps.heapPushMax(heap, 10); console.log("插入10后:", heap); // [10, 7, 5, 4, 3, 1, 2, 6] ``` ## 🌐 演示页面 项目包含一个完整的 HTML 演示页面 `index.html`,包含: - 所有核心功能的实时演示 - 堆排序步骤可视化 - 堆结构的可视化展示 - 详细的代码示例和说明 打开 `index.html` 即可在浏览器中查看所有功能的演示效果。 ## 📋 函数列表 ### 基础操作 - `siftDownMax` - 大顶堆下浮 - `siftDownMin` - 小顶堆下浮 - `siftDown` - 通用下浮 - `siftUpMax` - 大顶堆上浮 - `siftUpMin` - 小顶堆上浮 - `siftUp` - 通用上浮 ### 建堆 - `buildHeap` - 通用建堆 - `buildHeapMax` - 建大顶堆 - `buildHeapMin` - 建小顶堆 ### 排序 - `heapSort` - 通用堆排序 - `heapSortAsc` - 升序排序 - `heapSortDesc` - 降序排序 - `heapSortWithSteps` - 带步骤的堆排序 ### 查看 - `heapPeek` - 通用查看堆顶 - `heapPeekMax` - 查看大顶堆堆顶 - `heapPeekMin` - 查看小顶堆堆顶 ### 弹出 - `heapPop` - 通用弹出堆顶 - `heapPopMax` - 弹出大顶堆堆顶 - `heapPopMin` - 弹出小顶堆堆顶 ### 插入 - `heapPush` - 通用插入 - `heapPushMax` - 大顶堆插入 - `heapPushMin` - 小顶堆插入 ### 替换 - `heapReplace` - 通用替换堆顶 - `heapReplaceMax` - 替换大顶堆堆顶 - `heapReplaceMin` - 替换小顶堆堆顶 - `heapReplacePush` - 替换并上浮 - `heapReplacePushMax` - 大顶堆替换并上浮 - `heapReplacePushMin` - 小顶堆替换并上浮 ### Top K - `findTopK` - 通用 Top K - `findMaxK` - 找最大的 k 个 - `findMinK` - 找最小的 k 个 ## 📊 性能对比 | 操作 | 时间复杂度 | 空间复杂度 | |------|-----------|-----------| | 建堆 | O(n) | O(1) | | 堆排序 | O(n log n) | O(1) | | 查看堆顶 | O(1) | O(1) | | 弹出堆顶 | O(log n) | O(1) | | 插入元素 | O(log n) | O(1) | | 替换堆顶 | O(log n) | O(1) | | Top K 问题 | O(n log k) | O(k) | ## 🔧 兼容性 - **浏览器**:支持所有现代浏览器(IE9+) - **Node.js**:支持所有 Node.js 版本 - **移动端**:iOS Safari、Chrome Mobile 等 ## 📝 许可证 本项目采用 [Mulan PSL v2](http://license.coscl.org.cn/MulanPSL2) 许可证。 ``` Mulan Permissive Software License,Version 2 You can use, copy, modify, and distribute the software, as long as you keep the copyright notice and the license text. See http://license.coscl.org.cn/MulanPSL2 for more details. ``` ## 🤝 贡献 欢迎提交 Issue 和 Pull Request! ## 📧 联系方式 - 作者:Dawnice Tam - 邮箱:dawnice@yandex.com - 日期:2026-07-22 - 版本:1.0.0 --- **DTheaps** - 让堆操作变得简单高效!