堆与优先队列实现实时排行榜 / TopK 流

// 运行环境：Node.js 14+
// 保存为 dsa-l24.js，执行：node dsa-l24.js

class MinHeap {
  #h = []
  push(x) { this.#h.push(x); this.#siftUp(this.#h.length - 1) }
  pop() { if (!this.#h.length) return undefined; const t = this.#h[0], l = this.#h.pop(); if (this.#h.length) { this.#h[0] = l; this.#siftDown(0) } return t }
  peek() { return this.#h[0] }
  get size() { return this.#h.length }
  #siftUp(i) { while (i > 0) { const p = (i-1)>>1; if (this.#h[p] <= this.#h[i]) break; [this.#h[p], this.#h[i]] = [this.#h[i], this.#h[p]]; i = p } }
  #siftDown(i) { const n = this.#h.length; while (true) { let m = i, l = 2*i+1, r = 2*i+2; if (l < n && this.#h[l] < this.#h[m]) m = l; if (r < n && this.#h[r] < this.#h[m]) m = r; if (m === i) break; [this.#h[m], this.#h[i]] = [this.#h[i], this.#h[m]]; i = m } }
}

// 实时排行榜：保留分数最高的 K 名
class Leaderboard {
  constructor(k) { this.k = k; this.heap = new MinHeap() }
  submit(score) {
    this.heap.push(score)
    if (this.heap.size > this.k) this.heap.pop() // 超出则扔掉当前最小
  }
  topK() {
    const snapshot = [...this.heap['#h']]        // 复制堆数组
    return snapshot.sort((a, b) => b - a)         // 降序展示
  }
}

// 调用示例：模拟弹幕打分流
const lb = new Leaderboard(3)
;[88, 95, 70, 99, 82, 91].forEach(s => lb.submit(s))
console.log(lb.topK()) // [99, 95, 91]（前 3 高）