JS如何实现二叉堆（JavaScript实现最小二叉堆和优先队列） _优先队列

JavaScript如何实现最小堆？如何实现优先队列？
首先，堆（heap）是一种数据结构，优先队列（priority queue）也是一种数据结构，堆并不等于优先队列，但是堆一般是用来实现优先队列的。堆有两种形式：最小堆和最大堆，优先队列是一种元素带有权值的队列，关于对和优先队列的更多内容可以查看：优先队列和堆原理详解，本文详解使用JavaScript实现最小二叉堆，同样也是实现一个优先队列。

文章图片
一、二叉堆的基本概念一个二叉堆是一个带有一下属性的二叉树：

二叉堆是一个完全二叉树（除了叶子结点外，内部结点都被填满，而且叶子结点尽量往坐靠），这个二叉堆的属性使得它适合使用一个数组储存。
一个二叉堆可能是最小堆或最大堆，在一个最小堆中，根结点的关键字是其它所有结点关键字的最小值，也就是说，一个结点的关键字小于或等于其儿子关键字，最大堆和最小堆类似，本文主要是实现最小堆。

下面是最小二叉堆的两个实例：

文章图片
二、如何表示二叉堆？一个二叉堆是一个完全二叉树，二叉堆的经典表示方法是使用一个数组表示，其中：

根结点为数组的第一个元素A[0]。
其它结点中，第i个结点和数组索引元素对应的关系为：

A[(i – 1) / 2]	返回第i个结点的父结点
A[(2 * i) + 1]	返回第i个结点的左儿子结点
A[(2 * i) + 2]	返回第i个结点的右儿子结点

上表提供数组表示二叉堆的遍历方式，注意：使用二叉树表示二叉堆是一种逻辑表示方式，逻辑表示是数据结构和算法实现的主要依据，而使用数组表示二叉堆则是一种物理表示，也就是它在计算机中的实际形式，下图是一个二叉堆和对应数组表示：

文章图片
三、堆的应用有哪些？1、堆排序（heap sort）：堆排序使用二叉堆堆一个数组进行排序，使用时间为O(nlogn)。
2、优先队列：可以使用一个二叉堆有效地实现一个优先队列，因为二叉堆支持push()、top()、pop()、decreaseKey()等操作，时间为O(logn)，二项堆和斐波那契堆是二叉堆的推广，这两种堆有更好的时间界，以及支持union合并操作。
3、图论算法：在图论算法中，优先队列使用得比较多，例如Dijkstra最短路径算法和Prim最小生成树算法。
4、其它问题也可以使用二叉堆有效地解决，例如寻找数组中第k个最大或最小元素（选择问题），对一个几乎已经排好序的数组进行排序，合并k个已排序的数组等等。
四、最小堆的操作【JS如何实现二叉堆（JavaScript实现最小二叉堆和优先队列）】1、top()：返回堆顶元素，top()时间复杂度为O(1)。
2、pop()：释放堆顶元素，pop()时间复杂度为O(logn)，因为释放堆顶元素后需要对恢复堆的性质，也就是进行堆化heapify()。
3、decreaseKey()：降低关键字的值，时间复杂度为O(logn)，如果降低一个结点的关键字后，该结点的关键字仍然大于父结点，则不需要恢复堆属性的操作，否则需要向上遍历恢复堆属性。
4、push()：使用O(logn)的时间插入一个新的关键字，首先将该新的关键字添加到树的结尾，如果该关键字大于父结点关键字，则不需要再进行操作，否则需要向上遍历恢复堆属性。
5、delete()：使用O(logn)的时间删除第i个关键字，利用堆的性质，我们可以调用decreaseKey降低第i个关键字，降低的值为负无穷（或-1、0等），这样目标结点就会升到堆顶，这时调用pop()操作即可完成删除操作。
五、使用JavaScript实现最小二叉堆和优先队列下面是使用JavaScript实现二叉堆操作的完整源码：

// 二叉堆构造函数，capacity: 容量，compare: 比较函数，array: 数组 function BinaryHeap(capacity, compare, array){ if(array){ this.array = array.concat(); this.size = array.length; if(capacity < 3) this.capacity = this.size * 2; else this.capacity = capacity; this.compare = compare; } else{ if(capacity < 3) return null; this.array = new Array(capacity); this.size = 0; this.capacity = capacity; this.compare = compare; } }// 检查二叉堆是否已空 BinaryHeap.prototype.isEmpty = function(){ return this.size == 0; }// 获取结点i的父结点 BinaryHeap.prototype.parent = function(i){ return Math.floor((i - 1) / 2); }// 获取结点i的左儿子 BinaryHeap.prototype.left = function(i){ return 2 * i + 1; }// 获取结点i的右儿子 BinaryHeap.prototype.right = function(i){ return 2 * i + 2; }// 根据数组元素的索引进行交换 BinaryHeap.prototype.swap = function(i, j){ var temp = this.array[i]; this.array[i] = this.array[j]; this.array[j] = temp; }// 二叉堆push操作，往堆中添加一个新元素 BinaryHeap.prototype.push = function(T){ if(this.size == this.capacity){ console.log("overflow: could not push key."); return; } this.size++; var i = this.size - 1; this.array[i] = T; // 上滤操作，由下而上检查 while(i != 0 & & this.compare(this.array[i], this.array[this.parent(i)])){ this.swap(i, this.parent(i)); i = this.parent(i); } }// 获取堆顶元素 BinaryHeap.prototype.top = function(){ return this.array[0]; }// 堆化操作，修复二叉堆的性质，由上而下检查，又称为下滤操作 BinaryHeap.prototype.heapify = function(i){ var left = this.left(i); var right = this.right(i); var small = i; if(left < this.size & & this.compare(this.array[left], this.array[i])) small = left; if(right < this.size & & this.compare(this.array[right], this.array[small])) small = right; if(small != i){ this.swap(i, small); this.heapify(small); } }// 释放堆顶元素，将最后一个元素替换堆顶元素，然后进行下滤堆化操作 BinaryHeap.prototype.pop = function(){ if(this.size < = 0){ console.log("heap is empty."); return null; } if(this.size == 1){ this.size--; return this.array[0]; } var root = this.array[0]; this.array[0] = this.array[this.size - 1]; this.size--; this.heapify(0); return root; }// 降低第i个结点的关键字 BinaryHeap.prototype.decreaseKey = function(i, NT){ this.array[i] = NT; while(i != 0 & & this.compare(this.array[i], this.array[this.parent(i)])){ this.swap(i, this.parent(i)); i = this.parent(i); } }// 删除元素 BinaryHeap.prototype.delete = function(i){ // this.decreaseKey(i, Number.MIN_VALUE); // this.pop(); if(this.size < = 0){ console.log("heap is empty."); return; } if(this.size == 1){ this.size--; return; } this.array[i] = this.array[this.size - 1]; this.size--; this.heapify(i); }// 构建堆，用于使用一个数组构建堆的时候进行堆化操作 BinaryHeap.prototype.buildHeap = function(){ for(var i = Math.floor(this.size / 2); i >= 0; i--) this.heapify(i); }function compare(a, b){ return a < b; }function print(heap){ var str = ""; while(!heap.isEmpty()){ var value = http://www.srcmini.com/heap.top(); heap.pop(); str += value +" "; } console.log(str); }var heap = new BinaryHeap(20, compare); heap.push(95); heap.push(23); heap.push(47); heap.push(36); heap.push(75); print(heap); var array = [150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130]; var h = new BinaryHeap(20, compare, array); h.buildHeap(); print(h);