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.

Complexity

Time: O(log n)
Space: O(1) extra

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

Visual walkthrough

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

After popping the minimum, the last value moves to the root and sifts down by swapping with the smaller child.

Step 1 - Replace root

The saved minimum is 1; the last value 7 moves to the root before sifting down.

Step 2 - Swap with the smaller child

7 swaps with 2, producing the final heap [2, 4, 7, 9, 6].

Implementation notes

local heap = {1, 4, 2, 9, 6, 7} is a Lua table laid out as a 1-based min-heap.
heap_pop(heap) mutates that same table and returns the removed root value.
local smallest = heap[1] stores the popped value 1 before the root slot is changed.
heap[1] = table.remove(heap) removes the last table element, 7, and writes it into the root. The trace shows this intermediate heap as [7, 4, 2, 9, 6].
Sift-down starts with local parent = 1 and repeats in while true do.
Child slots use 1-based heap math: left = parent * 2 and right = left + 1.
if left > #heap then break end stops when the current parent has no children.
The code starts with the left child, then switches to the right child only when right <= #heap and heap[right] < heap[left].
This is a min-heap: if heap[parent] <= heap[child] then break end stops when the parent is already no larger than the smaller child.
Swaps use Lua multiple assignment: heap[parent], heap[child] = heap[child], heap[parent].
The replay has one sift-down swap: root 7 swaps with smaller child 2, producing [2, 4, 7, 9, 6].
print(tostring(popped) .. " -> " .. list_string(heap)) renders the returned value and final heap as 1 -> [2, 4, 7, 9, 6].

Output

1 -> [2, 4, 7, 9, 6]