编辑代码

/* 最小堆规则 */
function less(i: number, j: number): boolean {
    return i < j;
}

/* 最大堆规则 */
function greater(i: number, j: number): boolean {
    return i > j;
}

class Heap {
    private _items: number[];
    private _size: number;
    private compare: Function;

    constructor(compare: Function | undefined = undefined) {
        this._items = [];
        this._size = 0;
        this.compare = compare || this.defaultCmp;
    }

    public empty(): boolean {
        return this._size === 0;
    }

    public size(): number {
        return this._size;
    }

    public insert(item: number) {
        this._items[this._size++] = item;
        this.up();
    }

    public extract(): number | undefined {
        if (this.size() === 0) {
            return undefined;
        }
        let result: number = this._items[0];
        this.swap(this._items, 0, --this._size);
        this.down();
        return result;
    }

    private defaultCmp(i: number, j: number): boolean {
        return i < j;
    }

    private getLeft(parentIdx: number): number {
        return 2 * parentIdx + 1;
    }

    private getRight(parentIdx: number): number {
        return 2 * parentIdx + 2;
    }

    private getParent(childrenIdx: number): number {
        return Math.trunc((childrenIdx - 1) / 2);
    }

    private swap(arr: number[], i: number, j: number) {
        let tmp: number = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private up(): void {
        let c: number = this.size() - 1;
        let p: number = this.getParent(c);
        while (c > 0 && this.compare(this._items[c], this._items[p])) {
            this.swap(this._items, c, p);
            c = p;
            p = this.getParent(p);
        }
    }

    private down(): void {
        let p: number = 0;
        let c: number = this.getLeft(p);
        while (c < this.size()) {
            if (
                this.getRight(p) < this._size &&
                this.compare(this._items[this.getRight(p)], this._items[this.getLeft(p)])
            ) {
                c = this.getRight(p);
            }
            if (this.compare(this._items[p], this._items[c]) || this._items[p] === this._items[c]) {
                break;
            }
            this.swap(this._items, p, c);
            p = c;
            c = this.getLeft(c);
        }
    }
}

// const heap = new Heap(greater);

// heap.insert(1);
// heap.insert(99);
// heap.insert(6);
// heap.insert(15);
// heap.insert(4);
// heap.insert(11);
// heap.insert(12);
// heap.insert(2);

// while (!heap.empty()) {
//     let cur: number | undefined = heap.extract();
//     console.log(cur);
// }



function topK(arr: number[], k: number): void {
    const minHeap = new Heap(less);
    // const result: number[] = [];
    let i: number = 0;
    while (i < arr.length) {
        if (i < k) {
            minHeap.insert(arr[i++]);
        } else {
            minHeap.extract();
            minHeap.insert(arr[i++]);
        }
    }

    while (!minHeap.empty()) {
        let cur: number | undefined = minHeap.extract();
        // result.push(cur);
        console.log(cur);
    }

    // return result;
}

const arr: number[] = [1, 8, 2, 3, 7, 9, 10, 5];
topK(arr, 5);