优先队列

class PriorityQueue {
    constructor(data, cmp) {
        this.data = data
        this.cmp = cmp
        for (let i = data.length >> 1; i >= 0; --i) {
            this.down(i)
        }
    }
    down(i) {
        let left = 2 * i + 1
        while (left < this.data.length) {
            let temp
            if (left + 1) {
                temp = this.cmp(this.data[left + 1], this.data[i]) ? left + 1 : i
            }
            temp = this.cmp(this.data[temp], this.data[left]) ? temp : left
            if (temp === i) {
                break
            }
            this.swap(this.data, temp, i)
            i = temp
            left = 2 * i + 1
        }
    }
    up(i) {
        while (i >= 0) {
            const parent = (i - 1) >> 1
            if (this.cmp(this.data[i], this.data[parent])) {
                this.swap(this.data, parent, i)
                i = parent
            } else {
                break
            }
        }
    }
    push(val) {
        this.up(this.data.push(val) - 1)
    }
    poll() {
        this.swap(this.data, 0, this.data.length - 1)
        const top = this.data.pop()
        this.down(0)
        return top
    }

    swap(data, i, j) {
        const temp = data[i]
        data[i] = data[j]
        data[j] = temp
    }
}

const pq = new PriorityQueue([4, 2, 3, 5, 6, 1, 7, 8, 9], (a, b) => a - b > 0)
console.log('📌📌📌 ~ pq', pq)
console.log(pq.poll())
console.log(pq.poll())
console.log(pq.poll())
pq.push(10)
pq.push(20)
console.log(pq.poll())
console.log(pq.poll())
console.log(pq.poll())
console.log(pq.poll())

class PriorityQueue {
    constructor(data, cmp) {
        // 使用堆顶守卫，更方便上浮时父节点的获取 p = i >> 1, 子节点本身就比较好获取倒是无所谓
        this.data = [null, ...data]
        this.cmp = cmp
        for (let i = this.data.length >> 1; i > 0; --i) this.down(i) // 对除最后一层的子节点进行堆化初始化
    }
    get size() {
        return this.data.length - 1
    }
    swap(i, j) {
        ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
    }
    // 递归上浮和下沉
    down(i) {
        if (i === this.size) return
        const j = i
        const l = i << 1
        const r = l + 1
        if (l <= this.size && this.cmp(this.data[i], this.data[l])) i = l
        if (l <= this.size && this.cmp(this.data[i], this.data[r])) i = r
        if (i !== j) {
            this.swap(i, j)
            this.down(i)
        }
    }
    up(i) {
        if (i === 1) return
        const p = i >> 1
        if (this.cmp(this.data[p], this.data[i])) {
            this.swap(p, i)
            this.up(p)
        }
    }
    push(val) {
        this.up(this.data.push(val) - 1) // 加入队列后进行上浮处理
    }
    poll() {
        this.swap(1, this.size) // 先交换首尾，方便后面出队
        const top = this.data.pop()
        this.down(1)
        return top
    }
}