Heaps are a a specialized tree-based data structure designed to efficiently retrieve the highest priority element at any time.

This "priority" can mean the largest value, the smallest value, or the item with the earliest deadline, making heaps exceptionally versatile.

Heaps guarantee O(log n) time for insertion and removal and O(1) time for accessing the highest priority element.

Because of these properties, heaps are widely used in real-world systems including:

In this chapter, I’ll cover:

What is a Heap?

So, what exactly is a heap?

A heap is a special kind of binary tree optimized for fast access to the highest-priority element.

It follows two key rules:

1. Complete Binary Tree

This is what keeps the tree balanced and ensures operations like insertion and deletion are efficient.

2. Heap Property

Every heap must also satisfy the heap property, which comes in two flavors:

Max Heap

Min Heap

Representing a Heap

Even though a heap is conceptually a binary tree, we don’t usually store it using nodes and pointers like a typical tree. Instead, the most common and efficient way to represent a heap is with a simple array.

Because a heap is a complete binary tree (filled level by level, left to right), it maps perfectly into an array without wasting space.

This mapping allows us to navigate the heap without storing extra pointers, which makes the implementation simpler and faster.

Here:

Quick Example

Consider a max heap stored as:

This is why heaps are implemented using arrays — the structure lines up naturally and keeps the operations fast and simple.

Common Heap Operations

Now that you know how heaps are structured, let’s look at the core operation you’ll use in practice.

For the examples we will use a max-heap. The logic for a Min-Heap is identical; you just reverse the comparison operations.

1. Peek

This is the simplest and fastest operation.

2. Insert

When we add a new element, we must satisfy both heap properties:

It's easiest to satisfy the Complete Tree property first. We just add the new element to the very last available spot in the tree, which is simply the end of our array.

This, however, will almost certainly break the Heap Property. The new element might be larger than its parent. To fix this, we "bubble up" (or "percolate up") the new element.

We compare it to its parent; if it's larger, we swap them. We repeat this process—compare, swap, move up—until the new element finds its rightful place, either by being smaller than its new parent or by becoming the new root.

Here’s what it looks like in code:

Time Complexity is O(log n) because the height of a complete binary tree with n nodes is log_2(n). In the worst case, the new element must travel all the way from a leaf to the root. This path is, by definition, the height of the tree.

3. Extract Max: Remove the Top Element

This is the most common heap operation. It removes and returns the root element. Like insert, this operation must also preserve both heap properties.

Removing the root (index 0) is easy, but it leaves a hole at the top. This breaks the Complete Tree property.

To fix this, we use a clever trick:

To fix this, we "sift down" (or "heapify down") the new root. We compare it to its children. If it's smaller than either of them, we swap it with the larger of its two children (to ensure the largest value moves up). We repeat this process—compare, swap with largest child, move down—until the element finds its correct position (i.e., it's larger than both of its children, or it becomes a leaf).

Here’s how it looks in code:

Time Complexity: is O(log n). Just like insert, the operation follows a path from the root to a leaf. The length of this path is the tree's height, which is O(log n).

4. Build Heap (Heapify an Array)

Sometimes, you are given an entire unsorted array and need to convert it into a valid heap.

You could start with an empty heap and call insert() for each of the $n$ elements in the array. Since each insert is O(log n), this would take O(n log n) time. We can do much better!

We know that all leaf nodes (the entire second half of the array) are, by definition, already valid heaps of size 1. They have no children, so the heap property is trivially true.

The real work is with the non-leaf nodes (the first half of the array). If we can ensure that every non-leaf node satisfies the heap property relative to its children, the whole tree will become a valid heap. So, we iterate backwards from the last non-leaf node up to the root (index 0). For each of these nodes, we call heapifyDown(). This "sifts down" the element, allowing larger children to move up and restoring the local heap property. Because we start from the bottom, by the time we heapifyDown a node, we are guaranteed that its children are already valid heap roots themselves.

Here is how it works:

Time Complexity is O(n).

Why O(n) and not O(n log n)?

This is a classic analysis. It looks like O(n log n) because we call heapifyDown (an O(log n) operation) n/2 times. But this is a loose upper bound.

You are doing a lot of cheap work on the many nodes at the bottom and a small amount of expensive work on the few nodes at the top. The total cost is dominated by the linear number of nodes, not the logarithmic height.