Problem Statement
Explain how a min-heap works. How do you insert an element and extract the minimum element?
Explanation
A min-heap is a complete binary tree where the value of each node is less than or equal to the values of its children. The minimum element is always at the root, making min-heaps perfect for implementing priority queues.
The heap property states that for any node i, the value at i is less than or equal to values at its children. This property must be maintained after every insertion and deletion. Heaps are typically implemented using arrays for space efficiency, with parent-child relationships calculated using index formulas.
To insert an element, first add the new element at the end of the array to maintain the complete binary tree property. This may violate the heap property, so perform heapify-up also called bubble-up or percolate-up. Compare the new element with its parent. If the new element is smaller, swap them. Continue this process moving up the tree until the heap property is restored or you reach the root. Time complexity is O of log n as you traverse at most the height of the tree.
To extract the minimum element, the minimum is always the root at index 0. Remove and return this element. Replace the root with the last element in the array to maintain completeness. This likely violates the heap property, so perform heapify-down also called bubble-down or percolate-down. Compare the new root with its children. Swap with the smaller child if the root is larger. Continue this process moving down the tree until the heap property is restored or you reach a leaf. Time complexity is O of log n.
Heapify-up starts at the inserted position and moves toward the root. At each step, if current node is smaller than parent, swap and continue. Stop when current node is greater than or equal to parent or reach root.
Heapify-down starts at the root and moves toward leaves. At each step, find the smallest among current node and its children. If current is not smallest, swap with the smallest child and continue. Stop when current is smallest or reach a leaf.
Min-heaps are commonly used in Dijkstra's shortest path algorithm, heap sort, finding the k smallest elements efficiently, and implementing priority queues where tasks with lower priority values are processed first.