Min-Heap Pop (Sift Down)

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.

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

Complexity

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

Visual walkthrough

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].

C# DSA Implementation

                            basic.cs
                        

                            using System;
using System.Collections.Generic;
using System.Linq;
class Program {
    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    static void HeapInsert(List<int> heap, int value) {
        heap.Add(value);
        int child = heap.Count - 1;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (heap[parent] <= heap[child]) break;
            (heap[parent], heap[child]) = (heap[child], heap[parent]);
            child = parent;
        }
    }
    static int HeapPop(List<int> heap) {
        int smallest = heap[0];
        heap[0] = heap[^1];
        heap.RemoveAt(heap.Count - 1);
        int parent = 0;
        while (true) {
            int left = parent * 2 + 1, right = left + 1;
            if (left >= heap.Count) break;
            int child = left;
            if (right < heap.Count && heap[right] < heap[left]) child = right;
            if (heap[parent] <= heap[child]) break;
            (heap[parent], heap[child]) = (heap[child], heap[parent]);
            parent = child;
        }
        return smallest;
    }
    static void Main() { var heap = new List<int> {1, 4, 2, 9, 6, 7}; int popped = HeapPop(heap); Console.WriteLine($"{popped} -> {ListString(heap)}"); }
}

                        

Output

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

Implementation notes

List<int> is the array-backed heap store; its managed backing array is owned by the CLR and reclaimed by GC. heap[0] = heap[^1] copies the last int value into the root, then RemoveAt(heap.Count - 1) drops the last slot while the replay stays focused on the logical heap contents.
The sift-down loop uses integer child indexes: left = parent * 2 + 1 and right = left + 1. left >= heap.Count and right < heap.Count guard every indexed read, and the tuple swap moves values in place for the trace's single "swap 7 with smaller child 2" frame.