Min-Heap Pop (Sift Down)

Remove the minimum value, move the last item to the root, and sift downward.

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(log n)
Space: O(1) extra @end

sift down After removing the root, the last value moves to the root and swaps with the smaller child until order is restored.

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 = {1, 4, 2, 9, 6, 7}
local popped = heap_pop(heap)
print(tostring(popped) .. " -> " .. list_string(heap))

@end @output 1 -> [2, 4, 7, 9, 6] @end