Min-Heap Internal Structure

Problem How is a min-heap implemented internally?

Be ready to discuss

• The shape: a complete binary tree, which is exactly why it can be stored in a flat array with no pointers and no wasted slots.
• Index arithmetic: for a node at index i, children sit at 2i+1 and 2i+2 and the parent at floor((i-1)/2) - all computed, never stored.
• The heap property: every parent is <= both children, so the minimum is always at index 0; note this is a partial order, not a sorted array.
• peek: O(1), just read index 0.
• insert: append at the end, then sift-up - swap with the parent while smaller than it - O(log n) because the tree height is log n.
• extractMin: swap root with the last element, shrink the array, then sift-down the new root by repeatedly swapping with its smaller child - O(log n).
• Why sift-down must pick the smaller child: swapping with the larger one violates the heap property against the other subtree.
• Heapify: building a heap from n elements bottom-up is O(n), not O(n log n) - worth knowing why the naive analysis overcounts.
• Array-backed advantages: cache locality and zero allocation overhead versus a pointer-based tree.
• Related trade-offs: a heap gives O(1) min and O(log n) insert but O(n) arbitrary search; a BST gives O(log n) search but a slower min; decrease-key needs an index map.