Heap.js 技术文档

1. 安装指南

Heap.js 是一个使用 CoffeeScript/JavaScript 实现的二叉堆。它可以从 Python 的 heapq 模块移植而来。Heap.js 可以在浏览器或 Node.js 中使用。

浏览器使用：

你可以从这里下载脚本，并将其包含在你的网页中。

<script type="text/javascript" src="./heap.js"></script>

Node.js 使用：

通过 npm 安装：

npm install heap

然后引用它：

var Heap = require('heap');

2. 项目使用说明

Heap.js 暴露了一个名为 Heap 的类。

构造函数：Heap([cmp])

构造函数接收一个比较函数作为可选参数。如果省略，堆会构建为最小堆，即堆顶的元素是最小的。

如果提供了比较函数，堆将根据比较函数的返回值构建。

• 如果 cmp(a, b) < 0，则元素 a 会在 b 前面
• 如果 cmp(a, b) > 0，则元素 b 会在 a 前面

因此，比较函数的形式如下：

function cmp(a, b) {
  if (a 在 b 前面) {
    return -1;
  } 
  if (b 在 a 前面) {
    return 1;
  }
  return 0;
}

比较数字，只需：

function cmp(a, b) {
  return a - b;
}

实例方法

• push(item) (别名：insert)：将元素添加到堆。
• pop()：弹出并返回堆中的最小元素。
• peek() (别名：top / front)：返回堆中的最小元素。
• replace(item)：弹出当前最小的值并添加新的元素。这比先弹出再添加更高效，在固定大小的堆中使用更合适。注意返回的值可能比元素本身大！
• pushpop(item)：快速版本的一个推送后接一个弹出。
• heapify()：重建堆。当内部数据的优先级被修改时，此方法可能很有用。
• updateItem(item)：更新给定元素在堆中的位置。每次元素被修改时，都应该调用此函数。
• empty()：确定堆是否为空。
• size()：获取堆中存储的元素数量。
• toArray()：返回堆的数组表示形式（注意：数组是堆内部节点的浅拷贝）。
• clone() (别名：copy)：返回堆的一个克隆（注意：内部数据是原始数据的一个浅拷贝）。

静态方法

注意：所有静态方法都旨在应用于数组。

• push(array, item, [cmp])：将元素添加到数组，并保持堆的不变性。
• pop(array, [cmp])：弹出数组中的最小元素，并保持堆的不变性。
• replace(array, item, [cmp])：弹出当前最小的值并添加新的元素。这比先弹出再添加更高效，在固定大小的堆中使用更合适。注意返回的值可能比元素本身大！
• pushpop(array, item, [cmp])：快速版本的一个推送后接一个弹出。
• heapify(array, [cmp])：建立堆。
• updateItem(array, item, [cmp])：更新给定元素在堆中的位置。每次元素被修改时，都应该调用此函数。
• nlargest(array, n, [cmp])：查找数据集中的 n 个最大元素。
• nsmallest(array, n, [cmp])：查找数据集中的 n 个最小元素。

3. 项目API使用文档

Heap.js 的 API 使用非常直观，以下是几个示例：

推送和弹出

var heap = new Heap();
heap.push(3);
heap.push(1);
heap.push(2);
heap.pop(); // 返回 1

自定义比较函数

var heap = new Heap(function(a, b) {
    return a.foo - b.foo;
});
heap.push({foo: 3});
heap.push({foo: 1});
heap.push({foo: 2});
heap.pop(); // 返回 {foo: 1}

查找数组中的最大/最小元素

var array = [1, 3, 4, 2, 5];
Heap.nlargest(array, 3);  // 返回 [5, 4, 3]
Heap.nsmallest(array, 3); // 返回 [1, 2, 3]

4. 项目安装方式

Heap.js 可以通过 npm 安装到 Node.js 中：

npm install heap

或者在浏览器中直接引用下载的脚本：

<script type="text/javascript" src="./heap.js"></script>