AlgoViz
HomeHeap / Priority Queue

Implement Min Heap

Medium

Sift up on insert, sift down on extract

Problem

Implement a min-heap supporting insert, getMin, and extractMin using an array.

In simple words

Store as an array; float small values up on insert and sink the root down on removal.

The idea

Insert at the end and swap upwards while the new value is smaller than its parent. To extract, take the root, move the last element into its place, and swap downwards with the smaller child until the order holds. Both walks are one path of a complete tree, so both are O(log n).

The trick

  • Sift down must compare against the smaller of the two children, or the invariant breaks.
  • The root is the minimum; nothing else is in any particular order.
  • Insert and extract O(log n), getMin O(1).

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
1
2
0
1
2

Step 1 of 2. Here's the example — insert 3,1,2; extractMin Values: 3, 1, 2.

1/2
Optimal
timeO(log n)spaceO(n)
1insert(x): a.push(x); swimUp(last)2extractMin(): swap(0,last); m=a.pop(); sinkDown(0); return m

Input

array
[3, 1, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
insert 3,1,2; extractMin
Output:
1

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.