优先队列的应用

如何求前 K 个高频元素？

• 第一步: 用哈希表统计每个元素的出现次数;
• 第二步: 把 [元素, 频数] 建为以频数为优先级的大顶堆;
• 第三步: 连续弹出 k 次, 每次弹出的元素就是当前频数最高的元素;
• 复杂度: 建堆 O(n), 每次弹出 O(log n), 合计 O(n log n); 空间 O(n);

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }

  const heap: [number, number][] = [...freq.entries()]; // [元素, 频数]

  const siftDown = (n: number, i: number): void => {
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let max = i;
      if (left < n && heap[left][1] > heap[max][1]) max = left;
      if (right < n && heap[right][1] > heap[max][1]) max = right;
      if (max === i) break;
      [heap[i], heap[max]] = [heap[max], heap[i]];
      i = max;
    }
  };

  for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
    siftDown(heap.length, i);
  }

  const result: number[] = [];
  for (let i = 0; i < k; i++) {
    result.push(heap[0][0]);
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      siftDown(heap.length, 0);
    }
  }
  return result;
}

• 关键: 堆的比较依据是频数而不是元素值, 见 优先队列;
• 频数表本身的用法见 哈希表频数统计;