A heap is a tree-based data structure that retrieves the highest-priority element in constant time. "Priority" can mean the largest value, the smallest value, or any custom ordering (such as earliest deadline first).

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

These properties make heaps useful in many real-world systems, including:

This chapter covers:

A heap is a 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

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 index arithmetic maps cleanly to the parent-child relationships of the tree.

The core heap operations are peek, insert, extract, and build-heap.

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:

Satisfy the Complete Tree property first by adding the new element to the last available spot in the tree, which is the end of the 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:

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: 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. A bottom-up approach runs in O(n).

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.

In production code and interview solutions, you'll almost always use the language's built-in heap or priority queue instead of writing one from scratch. The implementations below are all backed by binary heaps with the standard complexities: O(log n) push/pop, O(1) peek.

One detail worth noting upfront: defaults differ across languages. Java, Python, and C# default to a min-heap (smallest element at the root). C++ and Rust default to a max-heap. Picking the wrong default is one of the most common bugs in heap-based interview answers.

Once you're comfortable with the built-in API in your language, most heap-based interview problems become straightforward: identify the priority, push the right elements, and pop in the right order.