Heap Operations

Table of Contents +

Say you are building a task list for an app. New tasks keep coming in. Each time, you want the most urgent one out first. Sorting the whole list every time a task arrives is slow. A heap fixes this exact pain. It always keeps the most important item ready at the top. Adding or removing an item stays fast.

In this tutorial we will do the three things you actually do with a heap. You put an item in. You take the top item out. You look at the top without removing it. We will use a min-heap. That is a heap where the smallest value sits at the root.

📚 A Quick Refresher

A heap is a binary tree that we store inside a plain array. No pointers. No nodes. Just an array and a little bit of index math.

Here is the index rule for any element sitting at index i:

Its parent is at (i - 1) / 2 (integer division).
Its left child is at 2 * i + 1.
Its right child is at 2 * i + 2.

In a min-heap there is one promise we must always keep. Every parent is smaller than or equal to its children. That promise is called the heap property. Every operation below exists to keep that promise true.

Let us see a small min-heap stored as an array [5, 9, 7, 14, 10].

See how the root 5 is the smallest? That is the value peek will hand you.

👀 Peek: Read the Top

Peek is the easy one. The smallest value in a min-heap is always at the root. The root is always at index 0. So peek just reads array[0]. Nothing moves.

The only thing to check first is whether the heap is empty. If it is, there is nothing to peek.

⬆️ Insert: Add, Then Sift Up

When you insert a value, you cannot just drop it anywhere. You have to add it and still keep the heap property true.

Here is the idea in plain points:

Put the new value at the very end of the array. This keeps the tree shape correct.
The new value might be smaller than its parent, which breaks the promise.
So we sift up: compare the new value with its parent, and if it is smaller, swap them.
Keep doing that, moving up the tree, until the parent is smaller or you reach the root.

Sift-up means walking a value upward toward the root. Each time it is too small to sit where it is, you swap it with its parent.

Steps to insert a value:

Add the value at the end of the array.
Set i to the index of that new value.
Look at the parent at (i - 1) / 2.
If i is not the root and array[i] is smaller than its parent, swap them.
Move i up to the parent index and repeat from step 3.
Stop when i is the root, or the parent is already smaller or equal.

Let us trace inserting 3 into [5, 9, 7, 14, 10].

Add 3 at the end: [5, 9, 7, 14, 10, 3]. Now 3 is at index 5.
Parent of index 5 is (5 - 1) / 2 = 2, which holds 7. Since 3 < 7, swap. Array becomes [5, 9, 3, 14, 10, 7]. Now 3 is at index 2.
Parent of index 2 is (2 - 1) / 2 = 0, which holds 5. Since 3 < 5, swap. Array becomes [3, 9, 5, 14, 10, 7]. Now 3 is at index 0.
3 is at the root now, so we stop. The smallest value moved all the way up to the root.

⬇️ Extract-Min: Remove the Top, Then Sift Down

Now the useful part. Extract-min takes out the smallest value and returns it. It does this while keeping the heap valid.

You might think “just remove index 0”. But then the root is empty and the whole tree falls apart. So we do a small trick instead.

Here is the idea in plain points:

Save array[0], because that is the answer we will return.
Move the last element into the root spot. Now the shape is correct again, but the root is probably too big.
Remove the last slot, since that value now lives at the root.
So we sift down: compare the root with its two children, and swap it with the smaller child if a child is smaller.
Keep doing that, moving down the tree, until both children are bigger or you reach the bottom.

Sift-down means walking a value downward. Each time, you swap it with its smaller child, until it sits in a spot where the heap property holds again.

Steps to extract the minimum:

If the heap is empty, there is nothing to extract.
Save array[0] as the result.
Move the last element into index 0, then remove the last slot.
Set i to 0.
Find the left child 2 * i + 1 and right child 2 * i + 2.
Pick the smaller of array[i] and its existing children, call its index smallest.
If smallest is not i, swap them, set i to smallest, and repeat from step 5.
Stop when no child is smaller. Return the saved result.

Let us trace extract-min on [3, 9, 5, 14, 10, 7].

Save 3 as the answer.
Move the last element 7 to the root: [7, 9, 5, 14, 10]. The size dropped to 5.
At index 0, value 7. Left child index 1 is 9, right child index 2 is 5. The smallest is 5 at index 2. Since 5 < 7, swap. Array becomes [5, 9, 7, 14, 10]. Now 7 is at index 2.
At index 2, value 7. Left child index 5 is out of range, right child index 6 is out of range. No children, so stop.
Return 3. The heap is [5, 9, 7, 14, 10] again, which is valid.

💻 Min-Heap in Code

Here is a full min-heap with insert, extractMin, and peek. We build a small heap, peek at the top, then pull values out one by one. Read the code first, then we will walk through it.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

class MinHeap:
    def __init__(self):
        self.heap = []

    # Add a value, then sift it up
    def insert(self, value):
        self.heap.append(value)         # put at the end
        i = len(self.heap) - 1
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] < self.heap[parent]:
                self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
                i = parent              # move up
            else:
                break                   # parent is smaller, done

    # Read the smallest value without removing it
    def peek(self):
        return self.heap[0]

    # Remove and return the smallest value, then sift down
    def extract_min(self):
        result = self.heap[0]               # the answer
        self.heap[0] = self.heap[-1]        # move last to root
        self.heap.pop()
        i = 0
        n = len(self.heap)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == i:
                break                       # children bigger, done
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest                    # move down
        return result

    def is_empty(self):
        return len(self.heap) == 0


h = MinHeap()
for v in [5, 9, 7, 14, 10, 3]:
    h.insert(v)

print("Top of heap (peek):", h.peek())
order = []
while not h.is_empty():
    order.append(h.extract_min())
print("Extracting in order:", " ".join(map(str, order)))

The output of the above code will be:

Top of heap (peek): 3
Extracting in order: 3 5 7 9 10 14

Notice the extract loop pulled values out in sorted order: 3 5 7 9 10 14. That happens because the smallest value always rises to the root. So each extract hands you the next smallest. The heap does the sorting for you, a little at a time.

⏱️ How Fast Are These Operations?

The height of a heap with n items is about log n. That is because the tree doubles in width at each level. Sift-up and sift-down both walk along that height. So insert and extract-min each do about log n steps in the worst case. Peek touches only the root, so it is always one step.

Tip

Insert and extract-min are both O(log n) because a value travels at most the height of the tree. Peek is O(1) because the answer always sits at index 0.

Here is the full picture.

Operation	What It Does	Time	Space
Peek	Read the root value	O(1)	O(1)
Insert	Add at end, then sift up	O(log n)	O(1)
Extract-min	Remove root, move last up, then sift down	O(log n)	O(1)

⚠️ Common Mistakes

New learners make the same small mistakes here. These are the ones to watch for:

Forgetting to move the last element to the root before sifting down. If you just delete index 0, you leave a hole and the heap breaks.
Picking the wrong child in sift-down. You must compare both children and swap with the smaller one, not just the left one.
Using the old size after a pop. When you extract, the size shrinks, so always compute child indices against the new size.
Peeking or extracting on an empty heap. Check for empty first, or you read a value that is not there.
Mixing up min and max. In a min-heap you sift up when the child is smaller. Flip every comparison for a max-heap.

🧩 What You’ve Learned

✅ A heap lives inside an array, and parent or child indices come from simple math on the position.

✅ Peek reads the root at index 0 in O(1) time and changes nothing.

✅ Insert adds the value at the end, then sifts it up by swapping with the parent while it is too small.

✅ Extract-min saves the root, moves the last element to the top, removes the last slot, then sifts down by swapping with the smaller child.

✅ Insert and extract-min run in O(log n) because a value moves at most the height of the tree.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Min Heap and Max Heap
Build a Heap

Previous Min Heap and Max Heap Next Build a Heap (Heapify)

Share & Connect

Share on LinkedIn