What Is a Heap?

The most important item, always on top

A priority queue lets you add items and always take out the most important one next. It's usually built as a heap.

Think of it like this: A hospital emergency room sees the most urgent patient next, not whoever arrived first.

The heap rule

In a max-heap, every parent is bigger than or equal to its children, so the biggest item is at the root. The tree is filled row by row, so it fits in a plain array:

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

int main() {
    vector<int> heap = {9, 7, 8, 3, 5, 6};
    /*        9
            /   \
           7     8
          / \   /
         3   5 6        */
    for (int i = 0; i < (int)heap.size(); i++) {
        cout << heap[i] << " -> children:";
        for (int c : {2 * i + 1, 2 * i + 2})
            if (c < (int)heap.size()) cout << ' ' << heap[c];
        cout << endl;
    }
    return 0;
}

Output

9 -> children: 7 8
7 -> children: 3 5
8 -> children: 6
3 -> children:
5 -> children:
6 -> children:

• push: add at the end, then swap upward while bigger than the parent (“sift up”).
• pop: remove the root, move the last item to the root, then swap it down with its bigger child (“sift down”).

The height is log n, so push and pop are O(log n); looking at the top is O(1).