Min Heap and Max Heap

Table of Contents +

Say you are building the “trending now” list on a video app. You always want the most-watched video sitting right on top. That way you can grab it fast. If you keep sorting the whole list again and again, it gets slow. A heap fixes this. A heap is a special tree that always keeps the smallest or the largest value at the very top. So you can read it in one step.

In this tutorial we look at the two flavors of heap. We see how we store a heap inside a plain array. And we learn the small index formulas that connect a node to its parent and children.

🌳 What Is a Heap?

A heap is a complete binary tree with one rule about ordering. Let me unpack that slowly.

A binary tree means every node has at most two children.
A complete binary tree means we fill the tree level by level, left to right, with no gaps. So the top fills first. Then the next row. And so on.
The heap rule says every parent keeps a fixed relationship with its children. Either the parent is always smaller, or the parent is always bigger.

That ordering rule is what splits heaps into two types.

⬇️⬆️ Min Heap vs Max Heap

The difference is just about who sits on top.

In a min heap, every parent is smaller than or equal to its children. So the smallest value of all is at the root, the very top.
In a max heap, every parent is larger than or equal to its children. So the largest value of all is at the root.

Here is a min heap. Notice the smallest number, 10, sits at the top.

And here is a max heap with the same numbers. Now the largest, 100, is on top.

Note

A heap is only ordered top to bottom, not left to right. So in a min heap the root is the smallest, but the second smallest could be either child. A heap is not a sorted list. It only promises one thing about the top.

📦 Storing a Heap in an Array

Here is the neat part. We do not need real tree nodes with pointers. Because a heap is always a complete binary tree with no gaps, we can just lay it out in an array, level by level.

Take that min heap from above. Read it top to bottom, left to right. You get this:

Index:  0    1    2    3    4    5
Value: 10   15   30   40   50  100

So the root goes at index 0. Its two children come next. Then their children. And so on. No gaps, because the tree had no gaps.

🧮 The Index Formulas

Now, if a node sits at index i, how do we find its family without any pointers? Three small formulas do all the work.

Left child is at 2*i + 1
Right child is at 2*i + 2
Parent is at (i - 1) / 2 using integer division (we drop the decimal part)

Let me show these on the array above. Take the root at index 0.

Left child is at 2*0 + 1 = 1, which holds 15. Correct.
Right child is at 2*0 + 2 = 2, which holds 30. Correct.

Now take index 1, the value 15.

Its parent is at (1 - 1) / 2 = 0, which holds 10. Correct.
Its left child is at 2*1 + 1 = 3, which holds 40. Correct.

This table walks every index of the min heap so you can see the pattern.

Index i	Value	Left (2i+1)	Right (2i+2)	Parent ((i-1)/2)
0	10	1 (15)	2 (30)	none
1	15	3 (40)	4 (50)	0 (10)
2	30	5 (100)	none	0 (10)
3	40	none	none	1 (15)
4	50	none	none	1 (15)
5	100	none	none	2 (30)

Tip

A child index counts as real only if it lands inside the array. If 2*i + 1 is greater than or equal to the array length, then that node simply has no left child. Same check for the right child.

🪜 Steps to Walk a Heap Array

Let us write a small program. It takes a min heap stored in an array and, for each node, prints its value, its parent, and its children using the formulas. Here is the plan we will follow.

Put the heap values in an array in level order.
Go through each index i from 0 to the last one.
Compute left as 2*i + 1 and right as 2*i + 2.
Compute parent as (i - 1) / 2, but only if i is not 0 (the root has no parent).
Before printing a child, check it is still inside the array. If not, print “none”.

💻 Code in 5 Languages

The code below builds the min heap array and prints the family of every node.

[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; }

# Print parent and children for each node in a heap array
def describe_heap(heap):
    n = len(heap)
    for i in range(n):
        left = 2 * i + 1   # left child index
        right = 2 * i + 2  # right child index
        print(f"Index {i} -> value {heap[i]}")

        if i == 0:
            print("  parent: none (root)")
        else:
            print(f"  parent: {heap[(i - 1) // 2]}")

        if left < n:
            print(f"  left child: {heap[left]}")
        else:
            print("  left child: none")

        if right < n:
            print(f"  right child: {heap[right]}")
        else:
            print("  right child: none")


heap = [10, 15, 30, 40, 50, 100]
describe_heap(heap)

The output of the above code will be:

Index 0 -> value 10
  parent: none (root)
  left child: 15
  right child: 30
Index 1 -> value 15
  parent: 10
  left child: 40
  right child: 50
Index 2 -> value 30
  parent: 10
  left child: 100
  right child: none
Index 3 -> value 40
  parent: 15
  left child: none
  right child: none
Index 4 -> value 50
  parent: 15
  left child: none
  right child: none
Index 5 -> value 100
  parent: 30
  left child: none
  right child: none

Note

One small thing about the parent formula in JavaScript and Python. Plain division can give a decimal, so we force whole-number division. In JavaScript we use Math.floor. In Python we use //. In C, C++, and Java, integer division already drops the decimal for us.

⏱️ Time and Space Complexity

Reading a node’s parent or child is just a tiny piece of arithmetic. So it costs the same no matter how big the heap gets. We call that constant time, written as O(1).

Operation	Time	Space
Find parent of a node	O(1)	O(1)
Find a child of a node	O(1)	O(1)
Walk the whole heap once	O(n)	O(1)
Store n values in the array	O(n)	O(n)

Tip

Moving between parent and child is O(1) because the formulas are just multiply and add. That speed is the whole reason we store a heap as an array instead of a tree full of pointers.

🧩 What You’ve Learned

✅ A heap is a complete binary tree with one ordering rule between every parent and its children.
✅ In a min heap the smallest value sits at the top. In a max heap the largest value sits at the top.
✅ A heap maps onto a plain array in level order, so no pointers are needed.
✅ For a node at index i: left child is 2*i + 1, right child is 2*i + 2, parent is (i - 1) / 2.
✅ Always check a child index is inside the array before using it, and remember the root at index 0 has no parent.
✅ Jumping between parent and child is O(1), which is why the array layout is so handy.

Check Your Knowledge

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

🚀 What’s Next?

Introduction to Heap
Heap Operations

Previous Introduction to Heap Next Heap Operations

Share & Connect

Share on LinkedIn