heap

手写实现 Heap 结构

文章参考

参考链接：二叉堆详解实现优先级队列

著作权归原作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Heap {
    data: ListNode[];
    comparator: Function;

    constructor(
        comparator = (a: ListNode, b: ListNode) => a.val < b.val,
        data = []
    ) {
        this.comparator = comparator;
        this.data = data;
        this.heapify();
    }

    // 堆化
    heapify() {
        // 1个或者0个，没必要堆化了
        if (this.size() < 2) return;

        // 这为啥从中间开始？值堆化一半就够了？
        for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
            this.bubbleDown(i);
        }
    }

    // 元素往上走
    bubbleUp(index: number) {
        while (index > 0) {
            const pIndex = (index - 1) >> 1; //注意：父节点位置，很有意思的一步

            // 往上走，所以要比较他和他爹谁大
            if (this.comparator(this.data[index], this.data[pIndex])) {
                this.swap(index, pIndex); //跟他爹换换位置
                index = pIndex;
            } else {
                break;
            }
        }
    }

    // 元素往下沉
    bubbleDown(index: number) {
        const lastIndex = this.size() - 1;

        while (true) {
            const leftIndex = index * 2 + 1; //左子节点index
            const rightIndex = index * 2 + 2; // 右子节点index
            let findIndex = index; //当前bubbleDown节点的位置

            // 左节点跟根节点对比，选择符合条件的
            if (
                leftIndex <= lastIndex &&
                this.comparator(this.data[leftIndex], this.data[findIndex])
            ) {
                findIndex = leftIndex;
            }

            // 右节点跟根节点对比，选择符合条件的上去
            if (
                rightIndex <= lastIndex &&
                this.comparator(this.data[rightIndex], this.data[findIndex])
            ) {
                findIndex = rightIndex;
            }

            // 说明有变化，做了交换
            if (index !== findIndex) {
                this.swap(index, findIndex);
                index = findIndex;
            } else {
                break;
            }
        }
    }

    // 交换两个元素位置
    swap(i: number, j: number) {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }

    // 返回堆顶元素
    peek() {
        return this.size() >= 0 ? this.data[0] : null;
    }

    // 往堆里面添加一个值
    offer(value: ListNode) {
        this.data.push(value); //添加一个元素，相当于放到了最右下角的子节点,index为数组最后一个
        this.bubbleUp(this.size() - 1);
    }

    // 移除堆顶元素，重新构建堆，返回删除的元素
    poll() {
        if (this.size() === 0) {
            return null;
        }
        // 把第一个扔到最后面去，然后把最后一个扔到第一个，然后让第1个往下沉。
        this.swap(0, this.size() - 1);
        let result = this.data.pop()!;
        this.bubbleDown(0);
        return result;
    }

    // 堆的大小
    size() {
        return this.data.length;
    }
}