堆的JavaScript实现_js写一个堆

由于JavaScript缺少内置的优先队列实现（例如Java的PriorityQueue，Python的heapq），导致刷题时碰到优先队列相关的题只能换语言写，还是自己写一个吧。

完整实现代码见 github

二叉堆可视化

概念

堆

作为前置知识，首先要了解一下堆的基本概念。

堆首先是一棵完全二叉树，也就是每层从左边依次填充的二叉树，由于这个特性，使它可以方便的由数组实现。

取一个数组arr，下标为0位置废弃不用，从1开始。那么对任意的下标i来说，它的父节点和左右子节点分别为

• 父节点：arr[i/2]
• 左子节点：arr[i*2]
• 右子节点：arr[i*2 + 1]

可以非常方便的寻找任意节点的父子节点，在堆的实现里是非常有用的特性。

堆除了拥有完全二叉树的特点之外，还有自己独有的特性，那就是一个节点要比它的左右两个子节点有更高（或相等）的 优先级。

优先级取决于使用者自己的定义，例如数字越小优先级越高，那么最小的值将出现在树的根节点，也可以看做是堆的“顶”，所以被称为 小顶堆（也有叫法为“小根堆”）。反之，则称为大顶堆。

在弹出数据时，堆总是弹出当前数据集中优先级最高的元素，也就是堆顶，这个特点能够完美匹配优先队列概念。

堆与优先队列

普通的队列是先进先出的，而优先队列则不同，它每次都会选择优先级最高的元素出队。

优先队列是一个逻辑上的数据结构，要想实现它可以采用很多种不同的方式。例如，一个有序链表就可以作为优先队列，入队时将元素插入合适位置，出队删除链表头并返回就可以了。

那么，为什么往往优先队列和堆总是放在一起，甚至一定程度上可以画上等号？

当然还是因为堆这种实现方式最契合于优先队列，以下是几种数据结构实现优先队列的复杂度。

---

优先队列ADT

要实现一个优先队列的基本功能，需要对外提供以下几个API：

class Heap {
   
  constructor(compare) {
   } //构造函数，能够接受自定义的优先级比较方法
  push(item) {
   } // 入队
  pop() {
   } // 返回优先级最高元素，出队
  peek() {
   } // 返回优先级最高元素，但不出队
  get size() {
   } // 当前队列的大小
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

实现

构造函数

构造函数只需要做两件事

1. 初始化用于存储堆数据的数组
2. 接受传入的优先级比较函数，没有则使用默认实现

  constructor(compare) {
   
    this.arr = [ 0 ]; // 下标从1开始好算，下标0废弃
    this.compare = (typeof compare === 'function') ? compare : this._defaultCompare;
  }
1
2
3
4
5

自定义比较函数

关于比较函数 compare ，要先明确它的定义。

与Array.sort()里的比较函数返回负数、0、正数三种状态不同，我在这里把 compare(a,b) 定义为 元素a是否比b有更高的优先级，更接近堆顶，返回bool值。即a更靠近堆顶，返回true，b更靠近堆顶则返回false。

这样写代码时可以不用纠结 compare 结果大于0小于0是什么含义，简化实现。

push

首先要实现的添加元素功能，方式为：

1. 新的元素添加到整个堆的末尾
2. 尝试让它进行“上浮”，回到它应该呆的位置

上浮操作是为了维护堆中元素总是比子节点优先级更高的性质。

具体操作也就是不断的将该元素与它的父节点比较优先级，如果新元素优先更高，理应更靠近堆顶，那么交换新元素和它父节点的位置。上浮一层之后继续执行，直到不满足比父节点优先级更高这一条件或者抵达堆顶。

(图：初始化 [4,3,2,1] 的大顶堆，执行 push(5)，将5插入到最后面，然后尝试上浮)

红色数字表示它们对应的数组下标

  push(item) {
   
    let {
    arr } = this;
    arr.push(item); //添加到末尾
    this._up(arr.length - 1); // 尝试上浮
  }

    /**
   * 上浮第k个元素
   * @param {int} k
   */
  _up(k) {
   
    let {
    arr, compare, _parent } = this;
    // k 比它的父节点更靠近堆顶，应该继续上浮（k=1 表示已经到达堆顶）
    while (k > 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17