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

JavaScript如何实现最小堆？如何实现优先队列？

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

一、二叉堆的基本概念

一个二叉堆是一个带有一下属性的二叉树：

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

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

二、如何表示二叉堆？

一个二叉堆是一个完全二叉树，二叉堆的经典表示方法是使用一个数组表示，其中：

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

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

三、堆的应用有哪些？

1、堆排序（heap sort）：堆排序使用二叉堆堆一个数组进行排序，使用时间为O(nlogn)。

2、优先队列：可以使用一个二叉堆有效地实现一个优先队列，因为二叉堆支持push()、top()、pop()、decreaseKey()等操作，时间为O(logn)，二项堆和斐波那契堆是二叉堆的推广，这两种堆有更好的时间界，以及支持union合并操作。

3、图论算法：在图论算法中，优先队列使用得比较多，例如Dijkstra最短路径算法和Prim最小生成树算法。

4、其它问题也可以使用二叉堆有效地解决，例如寻找数组中第k个最大或最小元素（选择问题），对一个几乎已经排好序的数组进行排序，合并k个已排序的数组等等。

四、最小堆的操作

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 = 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);