Introduction to Heap

Say you are building a hospital queue. Patients keep coming in. Each one has a severity number. Every time a doctor is free, you must hand over the most severe patient right now. The tricky part is that new patients keep arriving while old ones leave. So the “most severe” keeps changing.

You could keep the whole list sorted. But then every new patient forces you to sort it all over again. That is slow, and you pay that cost again and again. What you really want is a structure that always keeps the top item ready. You should not have to sort the whole thing each time. That structure is the heap.

🏥 A Real-World Way to Picture It

Think of an office where everyone reports to a boss above them. The rule is simple. A boss always earns more than the people directly under them. Nobody below a boss earns more than that boss.

Now you cannot tell who is the second highest or the tenth highest just by looking. But one thing is always true. The person at the very top is the highest earner in the whole company. So if someone asks “who earns the most?”, you do not search. You just point at the top.

A heap works the same way. It does not keep everything fully sorted. It only promises one thing. The top item is always the biggest, or always the smallest. That one promise is what makes it fast.

📚 What a Heap Actually Is

A heap is a special kind of binary tree. A binary tree is a structure where each node can have up to two children. A heap adds two extra rules on top of that.

• It is a complete binary tree. That means every level is fully filled, from left to right. Only the last level is allowed to be partly empty. There are no gaps in the middle.
• It follows the heap property. This is the parent-versus-child rule that keeps the top item special.

The heap property comes in two flavours:

• In a max-heap, every parent is bigger than or equal to its children. So the largest value sits at the root.
• In a min-heap, every parent is smaller than or equal to its children. So the smallest value sits at the root.

That is the whole idea. One root that is always the extreme value, and a tree that stays neatly filled.

Here is a small max-heap. Notice how every parent is bigger than its children, and the biggest value (50) sits right at the top.

🎯 Why We Even Need It

Let us go back to the pain. You need the largest or the smallest item, over and over, while items keep coming and going. Picture a few common cases:

• A music app picking the next most popular song to recommend.
• An operating system choosing which task to run next based on priority.
• A maps app like Uber picking the closest driver again and again.

In all of these, you do not want the whole list sorted. You only want the top one, and you want it fast. You also want adding a new item to stay cheap.

A heap fits this exactly. See how it compares to keeping a sorted list:

So a heap gives you the top item instantly. And inserting or removing stays at O(log n), which is very fast even for millions of items. A sorted list cannot match that. Keeping it sorted on every change costs O(n).

🧠 The Clever Trick: Store It in a Plain Array

Here is the part that surprises most people. A heap looks like a tree, but we usually do not build it with node objects and pointers. We just store it in a plain array. There is no tree-building work at all.

So how does an array hold a tree? Through simple index math. We fill the array level by level, left to right. That is the same order you read the tree. Then we find parent and child positions using formulas.

If a node sits at index i (using 0-based indexing), then:

• its left child is at index 2*i + 1,
• its right child is at index 2*i + 2,
• its parent is at index (i - 1) / 2 (whole-number division).

Let us map the max-heap from above into an array so you can see it click. Each box below is one array slot, shown in level-order from index 0 to index 5. These are positions in the array, not links between nodes.

So the array is [50, 30, 40, 10, 20, 35]. Check it yourself. The node 30 is at index 1. Its left child should be at 2*1 + 1 = 3, which holds 10. Its right child is at 2*1 + 2 = 4, which holds 20. The formula just works.

Let us write a tiny program. It takes a heap array and a chosen node, then prints that node’s parent and children using only the index math. No real tree needed.

#include <stdio.h>

// Show parent and children of a node using heap index math
void showRelations(int heap[], int size, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int parent = (i - 1) / 2;

    printf("Node at index %d = %d\n", i, heap[i]);
    if (i > 0)
        printf("  Parent  = %d\n", heap[parent]);
    if (left < size)
        printf("  Left    = %d\n", heap[left]);
    if (right < size)
        printf("  Right   = %d\n", heap[right]);
}

int main(void) {
    int heap[] = {50, 30, 40, 10, 20, 35};
    int size = 6;
    showRelations(heap, size, 1); // look at the node 30
    return 0;
}

Node at index 1 = 30
  Parent  = 50
  Left    = 10
  Right   = 20

#include <iostream>
#include <vector>
using namespace std;

// Show parent and children of a node using heap index math
void showRelations(const vector<int>& heap, int i) {
    int size = heap.size();
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int parent = (i - 1) / 2;

    cout << "Node at index " << i << " = " << heap[i] << "\n";
    if (i > 0)
        cout << "  Parent  = " << heap[parent] << "\n";
    if (left < size)
        cout << "  Left    = " << heap[left] << "\n";
    if (right < size)
        cout << "  Right   = " << heap[right] << "\n";
}

int main() {
    vector<int> heap = {50, 30, 40, 10, 20, 35};
    showRelations(heap, 1); // look at the node 30
    return 0;
}

Node at index 1 = 30
  Parent  = 50
  Left    = 10
  Right   = 20

public class HeapIndices {

    // Show parent and children of a node using heap index math
    static void showRelations(int[] heap, int i) {
        int size = heap.length;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int parent = (i - 1) / 2;

        System.out.println("Node at index " + i + " = " + heap[i]);
        if (i > 0)
            System.out.println("  Parent  = " + heap[parent]);
        if (left < size)
            System.out.println("  Left    = " + heap[left]);
        if (right < size)
            System.out.println("  Right   = " + heap[right]);
    }

    public static void main(String[] args) {
        int[] heap = {50, 30, 40, 10, 20, 35};
        showRelations(heap, 1); // look at the node 30
    }
}

Node at index 1 = 30
  Parent  = 50
  Left    = 10
  Right   = 20

# Show parent and children of a node using heap index math
def show_relations(heap, i):
    size = len(heap)
    left = 2 * i + 1
    right = 2 * i + 2
    parent = (i - 1) // 2

    print(f"Node at index {i} = {heap[i]}")
    if i > 0:
        print(f"  Parent  = {heap[parent]}")
    if left < size:
        print(f"  Left    = {heap[left]}")
    if right < size:
        print(f"  Right   = {heap[right]}")


heap = [50, 30, 40, 10, 20, 35]
show_relations(heap, 1)  # look at the node 30

Node at index 1 = 30
  Parent  = 50
  Left    = 10
  Right   = 20

// Show parent and children of a node using heap index math
function showRelations(heap, i) {
  const size = heap.length;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  const parent = Math.floor((i - 1) / 2);

  console.log(`Node at index ${i} = ${heap[i]}`);
  if (i > 0) console.log(`  Parent  = ${heap[parent]}`);
  if (left < size) console.log(`  Left    = ${heap[left]}`);
  if (right < size) console.log(`  Right   = ${heap[right]}`);
}

const heap = [50, 30, 40, 10, 20, 35];
showRelations(heap, 1); // look at the node 30

Node at index 1 = 30
  Parent  = 50
  Left    = 10
  Right   = 20

⚙️ What a Heap Powers

A heap is not just a textbook idea. It quietly runs many things you use every day.

• Priority queue. This is a priority queue, a queue where the most important item comes out first, not the oldest one. The hospital example from the start is exactly this. A heap is the usual way to build one.
• Heap sort. You can sort a whole array by pushing everything into a heap, then pulling out the top item one by one. Each pull gives the next biggest value in order.
• Top-K problems. Things like “find the 10 most-viewed videos” or “the 5 nearest restaurants” lean on heaps. The heap keeps only the items that matter.

🚫 Common Mistakes to Avoid

A few things trip up beginners with heaps. Keep these in mind:

• Thinking a heap is fully sorted. It is not. Only the root is guaranteed to be the extreme value.
• Mixing up min-heap and max-heap. Always know which one you are building, because the parent-child rule flips.
• Forgetting the “complete tree” rule. A heap fills left to right with no gaps. That is what lets the array index math work.
• Using the wrong index formula. With 0-based arrays the children are 2*i + 1 and 2*i + 2. With 1-based arrays they are 2*i and 2*i + 1. Pick one and stay with it.

🧩 What You’ve Learned

• ✅ A heap is a complete binary tree that follows the heap property.
• ✅ In a max-heap the parent is bigger than its children, so the largest value sits at the root. In a min-heap the parent is smaller, so the smallest sits at the root.
• ✅ A heap gives you the top item in O(1), and insert or remove in O(log n).
• ✅ We store a heap in a plain array and find parent and child by index math: children at 2*i + 1 and 2*i + 2, parent at (i - 1) / 2.
• ✅ Heaps power priority queues, heap sort, and top-K problems.

🚀 What’s Next?

• Min Heap and Max Heap
• Heap Operations