MinHeap.js

/*
 * 最小堆
 * 堆的本质是一种树形结构
 */
module.exports = class MinHeap {
    constructor() {
        this.data = [];
        this.count = 0;
    }
    // 初始化数组
    init(arr) {
        this.data = arr;
        this.count = arr.length;
        for(var i = Math.floor(this.count/2-1); i >= 0; i--) {
            this.shiftDown(i);
        }
    }
    // 提升元素
    // 把小的元素位置往上提升
    shiftUp(k) {
        while(k > 0 && this.data[Math.floor((k-1)/2)] > this.data[k]) {
            this.swap(this.data, Math.floor((k-1)/2), k);
            k = Math.floor((k-1)/2);
        }
    }
    // 下降元素
    // 当顶部弹出元素后，用于重新获得最小的元素
    shiftDown(k) {
        while(2*k+1 < this.count) {
            var j = 2*k+1;
            if(j+1 < this.count && this.data[j+1] < this.data[j]) {
                j++;
            }
            if(this.data[k] <= this.data[j]) break;
            this.swap(this.data, k, j);
            k = j;
        }
    }
    // 向最小堆中插入一个新元素
    insert(element) {
        this.data.push(element);
        this.shiftUp(this.count);
        this.count++;
    }
    // 从最小堆中取出堆顶元素
    extractMin() {
        var ret = this.data[0];
        this.swap(this.data, 0, this.count-1);
        this.count--;
        this.shiftDown(0);
        return ret;
    }
    // 获取最小堆中的堆顶元素
    getMin() {
        return this.data[0];
    }
    // 返回堆中元素的个数
    size() {
        return this.count;
    }
    // 判断当前堆中是否为空
    isEmpty() {
        return this.count === 0; 
    }
    // 交换元素
    swap(arr, a, b) {
        var t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}