Heaps: Introduction to the Heap Data Structure

A heap is a tree-shaped data structure that keeps its most important element — the smallest or the largest — instantly available at the root. It does this by enforcing a simple rule called the heap property between every parent and its children, rather than fully sorting the data. That cheaper-than-sorting guarantee is exactly what makes heaps the engine behind priority queues, heap sort, and many graph algorithms like Dijkstra’s.

The heap property

A heap is a complete binary tree (every level full except possibly the last, which fills left to right) that satisfies one ordering rule:

• Min-heap: every parent is ≤ its children. The minimum sits at the root.
• Max-heap: every parent is ≥ its children. The maximum sits at the root.

That’s the whole contract. Note what it does not promise: siblings are unordered, and the tree is not fully sorted. You only get a guarantee about the path from the root downward. This weaker promise is why a heap can be built and maintained far more cheaply than a sorted structure.

        min-heap                 max-heap
           1                        9
         /   \                    /   \
        3     2                  6     7
       / \   /                  / \   /
      7   4 5                  3   1 2

In the min-heap, 1 ≤ 3, 1 ≤ 2, 3 ≤ 7, and so on — every parent beats its children, yet 3 and 2 (siblings) are in no particular order.

Min-heap vs max-heap

They are mirror images. Anything you can do with one, you can do with the other by flipping the comparison. A common trick: to simulate a max-heap using a min-heap (or a min-heap-only library), negate the values on the way in and out.

For beginners: Think “min-heap = cheapest task first, max-heap = highest priority first.” Which one you want depends on whether small or large is “most important” for your problem.

Array representation: no pointers needed

The killer feature of a binary heap is that the complete-tree shape lets you store the whole thing in a flat array — no node objects, no child pointers. You read the array left to right, level by level. For a node at index i (0-based):

• parent(i) = (i - 1) / 2 (integer division)
• left(i) = 2*i + 1
• right(i) = 2*i + 2

So the array [1, 3, 2, 7, 4, 5] is the min-heap drawn above. Index 0 is the root 1; its children are at indices 1 and 2 (3 and 2); and so on.

int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

const parent = (i) => (i - 1) >> 1; // floor division by 2
const left   = (i) => 2 * i + 1;
const right  = (i) => 2 * i + 2;

def parent(i): return (i - 1) // 2
def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2

Going deeper: Some textbooks use a 1-based array (root at index 1), which gives the tidier parent = i/2, left = 2i, right = 2i+1. Both are valid — just stay consistent. This course uses 0-based indexing to match how arrays work in all four languages.

What heaps cost

Heaps are not for searching arbitrary values — that’s a job for a hash table or a BST. Reach for a heap whenever you repeatedly need the current min or max while items stream in and out.

When to use a heap

• You need the k largest/smallest items, or a running median.
• You’re scheduling by priority (OS task queues, Dijkstra, A*).
• You want to sort with a guaranteed O(n log n) and O(1) extra space (heap sort).

Next, see how the binary heap packs a tree into an array, then learn the core heap operations. Ready to practice? Try the heap exercises.