Top-K with a Heap

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

Algorithm

Steps

Store the heap in an array.
Compare parent and child indexes instead of building explicit tree nodes.
Swap only when the heap order is violated.
Print the deterministic final heap state for replay comparison.

Complexity

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

bounded heap For top-k largest values, a min-heap of size k keeps the current cutoff at the root.

Lua DSA Implementation

basic.lua

local function list_string(values) return "[" .. table.concat(values, ", ") .. "]" end
local function heap_insert(heap, value)
  table.insert(heap, value)
  local child = #heap
  while child > 1 do
    local parent = math.floor(child / 2)
    if heap[parent] <= heap[child] then break end
    heap[parent], heap[child] = heap[child], heap[parent]
    child = parent
  end
end
local function heap_pop(heap)
  local smallest = heap[1]
  heap[1] = table.remove(heap)
  local parent = 1
  while true do
    local left = parent * 2
    local right = left + 1
    if left > #heap then break end
    local child = left
    if right <= #heap and heap[right] < heap[left] then child = right end
    if heap[parent] <= heap[child] then break end
    heap[parent], heap[child] = heap[child], heap[parent]
    parent = child
  end
  return smallest
end
local heap = {}
for _, value in ipairs({5, 1, 9, 3, 7, 2}) do heap_insert(heap, value); if #heap > 3 then heap_pop(heap) end end
table.sort(heap, function(a, b) return a > b end)
print(list_string(heap))

Implementation notes

local heap = {} starts an empty Lua table used as a 1-based min-heap.
The pinned input is {5, 1, 9, 3, 7, 2}; the size limit is the literal check #heap > 3, so this run keeps the top 3 values.
ipairs(...) visits the input values in order, and each value is passed to heap_insert(heap, value).
heap_insert appends with table.insert(heap, value), then starts child = #heap.
Parent slots use 1-based heap math: parent = math.floor(child / 2).
The min-heap sift-up loop runs while child > 1 and stops when heap[parent] <= heap[child].
Swaps use Lua multiple assignment: heap[parent], heap[child] = heap[child], heap[parent].
After each insert, if #heap > 3 then heap_pop(heap) end removes the current heap root, keeping only three candidates.
heap_pop stores heap[1], replaces the root with table.remove(heap), then sifts down from parent = 1.
Sift-down uses left = parent * 2 and right = left + 1; the right child is chosen only when right <= #heap and heap[right] < heap[left].
The trace states are: after 5, [5]; after 1, [1, 5]; after 9, [1, 5, 9]; after 3 is inserted and 1 is popped, [3, 5, 9]; after 7 is inserted and 3 is popped, [5, 7, 9]; after 2 is inserted and immediately popped, [5, 7, 9].
table.sort(heap, function(a, b) return a > b end) sorts the surviving values high to low before printing.
print(list_string(heap)) uses table.concat through list_string, so the final output is [9, 7, 5].

Output

[9, 7, 5]