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. @end @complexity

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

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))

@end @output [9, 7, 5] @end