背景となる自社記事：ライブコーディング面接で問われる標準パターン。本稿ではそのうち Top K Frequent Elements だけを、実装と不変条件に絞って扱います。

TypeScriptでTop K Frequent Elementsを実装する：固定長最小ヒープの不変条件とテスト

nums に含まれる値のうち、出現回数が多い順に k 個を返す問題です。頻度表を作ってから全件をソートしても解けますが、異なる値の数を m とすると O(m log m) になります。

k が小さいときは、要素数を常に k 以下に保つ最小ヒープを使うと、選別部分を O(m log k) にできます。要点は「ヒープの根には、現在採用している候補の中で最小の頻度を置く」ことです。

先に結論：維持する不変条件

頻度 (value, count) を一件ずつ処理し、次の状態を維持します。

• ヒープの要素数は最大 k
• ヒープには、ここまでに見た頻度の大きい候補だけが入る
• 根はヒープ内で最小の count

ヒープがまだ k 個未満なら追加します。埋まった後は、候補の count が根より大きい場合だけ根を置き換えます。根以下の候補は、すでに k 個以上の候補に負けているため、以後の上位 k に入れません。

実装

以下は一ファイルで実行できる例です。replaceRoot のあとにだけ siftDown すればよく、配列全体を再ソートする必要はありません。

import { strict as assert } from "node:assert";

type Entry = { value: number; count: number };

class MinHeap {
  private readonly data: Entry[] = [];

  get size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  values() {
    return [...this.data];
  }

  push(entry: Entry) {
    this.data.push(entry);
    this.siftUp(this.data.length - 1);
  }

  replaceRoot(entry: Entry) {
    this.data[0] = entry;
    this.siftDown(0);
  }

  private siftUp(index: number) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.data[parent].count <= this.data[index].count) return;
      [this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
      index = parent;
    }
  }

  private siftDown(index: number) {
    while (true) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;

      if (left < this.size && this.data[left].count < this.data[smallest].count) smallest = left;
      if (right < this.size && this.data[right].count < this.data[smallest].count) smallest = right;
      if (smallest === index) return;
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

function topKFrequent(nums: number[], k: number): number[] {
  if (!Number.isInteger(k) || k < 1) throw new RangeError("k must be a positive integer");

  const counts = new Map<number, number>();
  for (const value of nums) counts.set(value, (counts.get(value) ?? 0) + 1);
  if (k > counts.size) throw new RangeError("k must not exceed the number of distinct values");

  const heap = new MinHeap();
  for (const [value, count] of counts) {
    const entry = { value, count };
    if (heap.size < k) heap.push(entry);
    else if (count > heap.peek().count) heap.replaceRoot(entry);
  }

  return heap
    .values()
    .sort((a, b) => b.count - a.count || a.value - b.value)
    .map(({ value }) => value);
}

assert.deepEqual(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2]);
assert.deepEqual(topKFrequent([3, 1, 2, 2, 3, 3, 1, 4], 2), [3, 1]);
assert.throws(() => topKFrequent([1], 0), RangeError);
console.log("topKFrequent tests passed");

bun top-k-frequent.ts で実行すると、次の出力になります。

topKFrequent tests passed

同じ頻度の値が境界にある場合、どの値を採るかは問題の仕様次第です。この例では候補の選別中に同点を置き換えず、返却時だけ値で安定した順序にしています。順位の二次条件が必要なら、count だけでなく value を比較関数に含めてください。

なぜ根との比較だけでよいのか

固定長の最小ヒープでは、根より小さい（または同じ）候補を採用しても、根以外の k - 1 個を押し出せません。反対に根より大きい候補は、現在の最下位候補を一つだけ置き換えればよいので、replaceRoot と下方向への調整で不変条件が戻ります。

この説明を先に置くと、面接で「なぜ最大ヒープではなく最小ヒープなのか」と聞かれても、k 個の候補の境界を根で即座に比較するため、と答えられます。

計算量と使い分け

n を入力長、m を異なる値の数とします。

処理	時間	追加メモリ
頻度表の作成	O(n)	O(m)
固定長ヒープでの選別	O(m log k)	O(k)
合計	O(n + m log k)	O(m + k)

k が m に近いなら、頻度表を配列にして一度ソートする実装の方が短く、実務では十分なこともあります。一方で、候補が非常に多く上位だけ欲しい場面では、固定長最小ヒープがそのまま使えます。

まとめ

Top K の本質は「全件を並べる」ことではなく、「今の上位 k 件の境界を安く保つ」ことです。最小ヒープの根を境界として扱い、置換後に siftDown する、という不変条件を押さえると、類題にもそのまま展開できます。