个性化阅读
专注于IT技术分析

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

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

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

JavaScript使用二叉堆实现优先队列

一、二叉堆的基本概念

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

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

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

最小二叉堆实例图解

二、如何表示二叉堆?

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

  1. 根结点为数组的第一个元素A[0]。
  2. 其它结点中,第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个已排序的数组等等。

四、最小堆的操作

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);
赞(0) 打赏
未经允许不得转载:srcmini » JS如何实现二叉堆?JavaScript实现最小二叉堆和优先队列
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏