heap

details

class Heap {
    constructor() {
        this.data = [];
    }
    parentIndex(index) {
        return ((index - 1) / 2) >> 0;
    }
    leftIndex(i) {
        return 2 * i + 1;
    }
    rightIndex(i) {
        return 2 * i + 2;
    }
    swap(i, j) {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }
    size() {
        return this.data.length;
    }
    insert(val) {
        this.data.push(val);
        this.heapifyUp();
    }
    peek() {
        return this.data.at(0);
    }
    heapifyUp() {
        let i = this.size() - 1;
        let pIndex = this.parentIndex(i);
        while (pIndex >= 0 && this.data[i] > this.data[pIndex]) {
            this.swap(i, pIndex);
            i = pIndex;
            pIndex = this.parentIndex(i);
        }
    }
    remove() {
        if (this.size() === 0) return null;
        if (this.size() === 1) return this.data.shift();
        const root = this.data.at(0);
        this.data[0] = this.data.pop();
        this.heapifyDown();
        return root;
    }
    heapifyDown() {
        let i = 0;
        while (this.leftIndex(i) < this.size()) {
            let maxIndex = this.leftIndex(i);
            if (this.rightIndex(i) < this.size() && this.data[this.rightIndex(i)] > this.data[maxIndex]) {
                maxIndex = this.rightIndex(i);
            }

            if (this.data[i] < this.data[maxIndex]) {
                this.swap(i, maxIndex);
                i = maxIndex;
            } else {
                break;
            }
        }
    }
}

// 测试用例
const maxHeap = new Heap();
maxHeap.insert(3);
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(6);
maxHeap.insert(7);

console.log('Max value (extract):', maxHeap.remove()); // 10
console.log('Current max (peek):', maxHeap.peek()); // 7
console.log('Max value (extract):', maxHeap.remove()); // 7

构建最大堆

details

function buildMaxHeap(arr) {
    // 从最后一个非叶子节点开始
    let parentIndex = ((arr.length - 2) / 2) >> 0;
    while (parentIndex >= 0) {
        maxHeapify(arr, parentIndex, arr.length);
        parentIndex--;
    }
}

function maxHeapify(arr, index, heapSize) {
    let left = 2 * index + 1; // 左子节点
    let right = 2 * index + 2; // 右子节点
    let largest = index; // 初始化最大元素为当前节点

    // 如果左子节点比当前节点大，则更新最大元素为左子节点
    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left;
    }

    //  如果右子节点比最大元素大，则更新最大元素为右子节点
    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大元素不是当前节点，则交换当前节点和最大元素的位置，并递归地对交换后的子树进行堆化
    if (largest !== index) {
        [arr[index], arr[largest]] = [arr[largest], arr[index]];
        // 递归地对受影响的子树进行最大堆化
        maxHeapify(arr, largest, heapSize);
    }
}