Top K Frequent Elements: Bucket Sort vs Heap, Measured

The advice you get on this problem is always the same shape. A min-heap of size k is O(n log k). Bucket sort is O(n). Therefore bucket sort wins. I wrote both, ran them against a 2-million-element array, and the comparison turned out to hinge on a line that none of the write-ups discuss: the number you pass to new Array() when you build the buckets.

Everything below was measured on Node 22.23.2, x86-64 Linux, with process.hrtime.bigint() and two warm-up calls before each timed loop. The scripts are in the article; you can paste them into one file and run them.

Counting is most of the bill

Both approaches start identically, and that shared prefix is where the time goes.

const countFrequencies = (nums) => {
  const freq = new Map();
  for (const num of nums) freq.set(num, (freq.get(num) ?? 0) + 1);
  return freq;
};

On two million integers drawn uniformly from [0, 500000) — 490,898 distinct values, maximum frequency 16 — that loop alone takes 190 ms. The selection step that follows it, the part the whole heap-versus-bucket argument is about, costs this much on the same prebuilt map:

Two things to notice before going further. The counting pass is 190 ms and dwarfs most of that column, so if you want this faster the first thing to attack is the Map, not the selection. And the heap's log k is visible — a clean 4x from k = 10 to k = 100,000 — while the bucket scan is flat, because it stops as soon as it has k values.

The heap, and the eviction line people get wrong

const topKHeap = (nums, k) => {
  const freq = countFrequencies(nums);
  const heap = []; // [count, value], min-heap ordered on count
 
  const siftUp = (start) => {
    let i = start;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  };
 
  const siftDown = () => {
    let i = 0;
    for (;;) {
      const left = 2 * i + 1;
      const right = left + 1;
      let smallest = i;
      if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
      if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
      if (smallest === i) return;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  };
 
  for (const [value, count] of freq) {
    heap.push([count, value]);
    siftUp(heap.length - 1);
    if (heap.length > k) {
      const last = heap.pop();
      if (heap.length > 0) { heap[0] = last; siftDown(); }
    }
  }
 
  return heap.sort((a, b) => b[0] - a[0]).map(([, value]) => value);
};

Note the complexity honestly: the loop runs once per distinct value, not once per element. It is O(u log k) where u is the number of unique values, plus the O(n) counting pass. Writing O(n log k) overstates the selection cost whenever u is much smaller than n, which is the common case. The final sort is over at most k items, so it is O(k log k) and does not change the class.

The bucket array, sized by the wrong number

The bucket idea: no value can occur more than n times, so frequencies are small integers and can be used directly as array indices. That is true. It is also weaker than what you need. The bound that matters is the actual maximum frequency, and it is sitting right there in the map you just built.

const topKBucket = (nums, k) => {
  const freq = countFrequencies(nums);
 
  let maxCount = 0;
  for (const count of freq.values()) if (count > maxCount) maxCount = count;
 
  const buckets = new Array(maxCount + 1); // sparse; holes cost nothing
  for (const [value, count] of freq) {
    (buckets[count] ??= []).push(value);
  }
 
  const result = [];
  for (let count = maxCount; count >= 1 && result.length < k; count--) {
    const bucket = buckets[count];
    if (bucket === undefined) continue;
    for (const value of bucket) {
      result.push(value);
      if (result.length === k) return result;
    }
  }
  return result;
};

The canonical published version writes new Array(nums.length + 1).fill(null).map(() => []). On the sample above that materialises 2,000,001 empty array objects to hold values whose frequencies never exceed 16, and then scans all two million slots from the top looking for the first non-empty one. It is still O(n). It is also, on this input, slower than the heap it is supposed to beat.

Skewed inputs make it grotesque. Ten million elements drawn from ten distinct values, k = 3: the nums.length + 1 version takes 725 ms, the maxCount + 1 version takes 1.8 ms. Same asymptotics, 400x apart, and the whole difference is one expression.

Ties make the two answers genuinely different

Before timing anything, check that the two functions even compute the same thing. They do not, and not because either is wrong.

const assert = (cond, msg) => { if (!cond) throw new Error(msg); };
 
const referenceTopK = (nums, k) => {
  const freq = countFrequencies(nums);
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1] || a[0] - b[0])
    .slice(0, k)
    .map(([value]) => value);
};
 
const countsOf = (values, freq) => values.map((v) => freq.get(v));
 
const runDifferential = (trials) => {
  let disagreed = 0;
  for (let t = 0; t < trials; t++) {
    const n = 1 + Math.floor(Math.random() * 40);
    const domain = 1 + Math.floor(Math.random() * 10);
    const nums = Array.from({ length: n }, () => Math.floor(Math.random() * domain));
    const freq = countFrequencies(nums);
    const k = 1 + Math.floor(Math.random() * freq.size);
 
    const want = countsOf(referenceTopK(nums, k), freq);
    const fromHeap = countsOf(topKHeap(nums, k), freq);
    const fromBucket = countsOf(topKBucket(nums, k), freq);
 
    assert(fromHeap.length === k, `heap returned ${fromHeap.length}, expected ${k}`);
    assert(fromBucket.length === k, `bucket returned ${fromBucket.length}, expected ${k}`);
    assert(fromHeap.join() === want.join(), `heap counts ${fromHeap} != ${want}`);
    assert(fromBucket.join() === want.join(), `bucket counts ${fromBucket} != ${want}`);
 
    const a = topKHeap(nums, k).slice().sort((x, y) => x - y).join();
    const b = topKBucket(nums, k).slice().sort((x, y) => x - y).join();
    if (a !== b) disagreed++;
  }
  return disagreed;
};
 
console.log(`disagreements: ${runDifferential(20000)}`);

Twenty thousand random cases, three runs. Zero assertion failures in any of them — both functions always return k values whose frequency profile matches the reference exactly. And 5,113 / 5,132 / 5,147 of those cases returned different sets of values. When values 7 and 9 both appear twice and only one slot is left, the heap keeps whichever the Map iteration order fed it first and the eviction order preserved; the buckets keep whichever landed earlier in buckets[2]. Both are defensible answers to "top k by frequency".

The thing to take from that is what you can assert in a test. The multiset of counts is deterministic and worth asserting. The identity of tied values is not, and a test that pins it is a test that will fail when you swap implementations. LeetCode 347 states the answer may be returned in any order for exactly this reason. Neither of my functions guarantees descending frequency order either — the heap's trailing sort happens to give it, the bucket scan happens to give it, and neither is contractual once you start slicing at a tie boundary.

One variable: how many buckets you allocate

Now the experiment that the complexity classes cannot answer. Both selection routines get the same prebuilt frequency map, so counting is excluded and only the part under discussion is timed. The bucket routine takes its array size as a parameter, so the sweep isolates that single choice.

const timeMs = (fn, reps) => {
  fn(); fn();
  const start = process.hrtime.bigint();
  for (let i = 0; i < reps; i++) fn();
  return Number(process.hrtime.bigint() - start) / reps / 1e6;
};
 
const heapSelect = (freq, k) => {
  const heap = [];
  const siftUp = (s) => { let i = s;
    while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const siftDown = () => { let i = 0;
    for (;;) { const l = 2 * i + 1, r = l + 1; let s = i;
      if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
      if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
      if (s === i) return; [heap[i], heap[s]] = [heap[s], heap[i]]; i = s; } };
  for (const [value, count] of freq) {
    heap.push([count, value]); siftUp(heap.length - 1);
    if (heap.length > k) {
      const last = heap.pop();
      if (heap.length > 0) { heap[0] = last; siftDown(); }
    }
  }
  return heap.sort((a, b) => b[0] - a[0]).map(([, v]) => v);
};
 
const bucketSelect = (freq, k, arraySize) => {
  const buckets = new Array(arraySize + 1).fill(null).map(() => []);
  for (const [value, count] of freq) buckets[count].push(value);
  const result = [];
  for (let i = arraySize; i >= 1 && result.length < k; i--) {
    for (const value of buckets[i]) { result.push(value); if (result.length === k) return result; }
  }
  return result;
};
 
const u = 1_000_000, k = 10;
const freq = new Map();
for (let i = 0; i < u; i++) freq.set(i, 1 + Math.floor(Math.random() * 20));
 
console.log(`heap select: ${timeMs(() => heapSelect(freq, k), 5).toFixed(0)} ms`);
for (const size of [20, 500_000, 1_000_000, 2_000_000, 2_500_000, 3_000_000, 3_500_000]) {
  console.log(`buckets ${size} (${(size / u).toFixed(2)}x u): ${timeMs(() => bucketSelect(freq, k, size), 5).toFixed(0)} ms`);
}

One million distinct values, k = 10. Medians of five runs; heap select came in at 82, 82, 82, 83, 83 ms, so treat anything within about 5 ms as a tie.

Sized by maxCount + 1, bucket selection is 3.6x faster than the heap at these sizes, and the table in the first section already showed its cost holding flat across four orders of magnitude of k. There is no k at which the correctly-sized bucket loses.

Sized by nums.length + 1, a crossover appears, and it is a crossover in the input shape rather than in k. Bucket selection draws level with the heap at a bucket array of 2,000,000 — twice the distinct-value count — and loses from there. Since that version sizes the array by nums.length, the threshold is n ≈ 2u: the average value repeating about twice. Raising k pushes the threshold further out, because the heap's cost grows with k and the bucket's does not: rerun the same sweep with k = 1000 and heap select goes to 160 ms while every bucket row is unchanged, so the bucket stays ahead through 3.5x. So the published version's advantage exists only for inputs where almost nothing repeats, which is the one case where nobody needs a top-k algorithm.

The O(k) memory argument survives all of this, and it is the honest reason to reach for the heap. A size-k heap holds k entries; the bucket array holds maxCount + 1 slots. If you are consuming a stream and cannot materialise a frequency map, or maxCount is unbounded, the heap is the only one of the two that still works.

The number that decides it