二叉堆(BinaryHeap)

使用完全二叉树实现堆结构，又称完全二叉堆，一般使用数组实现

• 对于根节点下标是 0 的元素
• 父节点为(i-1)>>1
• 左子节点为 2*i+1
• 右子节点为 2*i+2

核心代码

import { Comparator, throwError, ERROR_EMPTY_ELEMENT, ErrorEnum } from '@/shared';

export interface IBinaryHeap<T> {
    /* 当前链表含有的节点数  */
    size: number;
    /* 获取堆顶元素 */
    top(): T;
    /* 往堆中添加一个元素 */
    add(val: T): void;
    /* 从堆顶删除一个元素 */
    remove(): T;
}
export class BinaryHeap<T> implements IBinaryHeap<T> {
    get size() {
        return this.list.length;
    }
    private list: T[] = [];
    constructor(private compare: Comparator<T>) {}
    top() {
        this.checkRange();
        return this.list[0];
    }
    add(val: T): void {
        this.list.push(val);
        this.shiftUp(this.size - 1);
    }
    remove(): T {
        this.checkRange();
        const val = this.list.shift()!;
        if (this.size !== 0) {
            this.list.unshift(this.list.pop()!);
            this.shiftDown(0);
        }
        return val;
    }
    private shiftUp(index: number): void {
        if (index === 0) return;
        const parentIndex = (index - 1) >> 1;
        if (this.compare(this.list[index], this.list[parentIndex]) > 0) {
            [this.list[index], this.list[parentIndex]] = [this.list[parentIndex], this.list[index]];
            this.shiftUp(parentIndex);
        }
    }
    private shiftDown(index: number): void {
        let childIndex = index * 2 + 1;
        if (childIndex >= this.size) return;
        if (
            childIndex + 1 < this.size &&
            this.compare(this.list[childIndex + 1], this.list[childIndex]) > 0
        )
            childIndex++;
        if (this.compare(this.list[childIndex], this.list[index]) > 0) {
            [this.list[index], this.list[childIndex]] = [this.list[childIndex], this.list[index]];
            this.shiftDown(childIndex);
        }
    }
    private checkRange() {
        if (this.size === 0) throwError(ERROR_EMPTY_ELEMENT, ErrorEnum.range);
    }
}