编辑代码

class Heap<T> {
    arr: Array<T>
    cmp: (a: T, b: T) => boolean
    constructor(arr: Array<T>, cmp: (a:T, b:T) => boolean) {
        this.arr = arr
        this.cmp = cmp
    }
    get size(): number {
        return this.arr.length
    }
    heapify() {
        if(this.size <= 1) return
        for(let i = 1; i < this.size; i ++) {
            this.bubbleUp(i)
        }
    }
    pop() {
        if(this.size === 0) return null
        if(this.size === 1) return this.arr.pop()
        let res = this.arr[0]
        this.arr[0] = this.arr.pop() as any
        this.bubbleDown(0)
        return res
    }
    swap(i: number, j: number) {
        [this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]]
    }
    push(val: T): void {
        this.arr.push(val)
        this.bubbleUp(this.size - 1)
    }
    bubbleUp(i: number) {
        while(i) {
            let p = Math.floor((i-1)/2)
            if(this.cmp(this.arr[i], this.arr[p])) {
                this.swap(i, p)
                i = p
            } else break
        }
    }
    bubbleDown(i: number) {
        while(i < this.size) {
            let j = i
            let l = i*2+1, r = i*2+2
            if(l < this.size && this.cmp(this.arr[l], this.arr[j])) {
                j = l
            }
            if(r < this.size && this.cmp(this.arr[r], this.arr[j])) {
                j = r
            }
            if(j > i) {
                this.swap(i, j)
                i = j
            } else break
        }
    }
}
function getMax(arr: number[], idx: number) {
    let heap = new Heap<number>([], (a: number, b: number) => a>b)
    for(let n of arr) {
        heap.push(n)
    }
    while(idx -- > 1) {
        heap.pop()
    }
    return heap.pop()
}

console.log(getMax([3,5,76,1,2,4,8,63,13,5,3], 2))
console.log(getMax([3,5,76,1,2,4,8,63,13,5,3], 3))