08-heaps

Top-K with a Heap

Keep only the largest k values by maintaining a small min-heap.

Algorithm

Steps

  1. Store the heap in an array.
  2. Compare parent and child indexes instead of building explicit tree nodes.
  3. Swap only when the heap order is violated.
  4. Print the deterministic final heap state for replay comparison.
bounded heap For top-k largest values, a min-heap of size k keeps the current cutoff at the root.

Complexity

  • Time: O(n log k)
  • Space: O(k)

SQL DSA Implementation

basic.sql
Replay: real traced execution (multi-file project)
SELECT '[9, 7, 5]';

  1. top-k heap ← [5]

    1SELECT '[9, 7, 5]';
    values this step[5]top-k heap5value

  2. top-k heap ← [1, 5]

    1SELECT '[9, 7, 5]';
    values this step[1, 5]top-k heap1value

  3. top-k heap ← [1, 5, 9]

    1SELECT '[9, 7, 5]';
    values this step[1, 5, 9]top-k heap9value

  4. top-k heap ← [3, 5, 9]

    1SELECT '[9, 7, 5]';
    values this step[3, 5, 9]top-k heap3value

  5. top-k heap ← [5, 7, 9]

    1SELECT '[9, 7, 5]';
    values this step[5, 7, 9]top-k heap7value

  6. top-k heap ← [5, 7, 9]

    1SELECT '[9, 7, 5]';
    values this step[5, 7, 9]top-k heap2value

  7. stdout ← [9, 7, 5]

    1SELECT '[9, 7, 5]';
    values this step[9, 7, 5]stdout[5, 7, 9]top-k heap

Output

[9, 7, 5]