最小堆-完整代码

class MinHeap {
    constructor(options = {}) {
        this.heap = [];
        this.priority = options.priority || ((x) => x); //priority compare function
    }

    insert(value) {
        if (value === null) return false;
        this.heap.push(value);
        this.siftUp(this.heap.length - 1);
        return true;
    }

    siftUp(index) {
        let parent = Math.floor((index - 1) / 2);
        while (index > 0 && this.priority(this.heap[parent]) > this.priority(this.heap[index])) {
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
            parent = Math.floor((index - 1) / 2);
        }
    }

    extract() {
        if (this.heap.length === 0) return undefined;
        if (this.heap.length === 1) return this.heap.shift();
        const minValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return minValue;
    }

    siftDown(index) {
        let child = index;
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        if (left < this.heap.length && this.priority(this.heap[left]) < this.priority(this.heap[child])) {
            child = left;
        }
        if (right < this.heap.length && this.priority(this.heap[right]) < this.priority(this.heap[child])) {
            child = right;
        }
        if (child !== index) {
            [this.heap[child], this.heap[index]] = [this.heap[index], this.heap[child]];
            this.siftDown(child);
        }
    }

    getMinium() {
        return this.heap.length == 0 ? undefined : this.heap[0];
    }

    size() {
        return this.heap.length;
    }
}

(() => {
    const minHeap = new MinHeap({priority: x => x[0]});
    for (let i = 7; i >= 0; i--) {
        minHeap.insert([i, String.fromCharCode(65 + i)]);
    }
    console.log(minHeap.getMinium());
    while(minHeap.size() > 0) {
        console.log(minHeap.extract());
    }
})()