Heap Data Structure | Interview Cake

Quick reference

	Worst Case
get min
remove min
insert
heapify
space

A binary heap is a binary tree where the smallest value is always at the top.

A binary heap is a binary tree where the nodes are organized to so that the smallest value is always at the top.

A min-heap has the smallest value at the top. A max-heap has the largest value at the top. We'll describe min-heaps here, but the implementation for max-heaps is nearly identical.

Strengths:

Quickly access the smallest item. Binary heaps allow you to grab the smallest item (the root) in time, while keeping other operations relatively cheap ( time).
Space efficient. Binary heaps are usually implemented with lists, saving the overhead cost of storing pointers to child nodes.

Weaknesses

Limited interface. Binary heaps only provide easy access to the smallest item. Finding other items in the heap takes time, since we have to iterate through all the nodes.

Uses

Priority queues are often implemented using heaps. Items are enqueued by adding them to the heap, and the highest-priority item can quickly be grabbed from the top.
One way to efficiently sort a list of items is to make a heap out of them and then remove items one at a time—in sorted order.

Implementation

Heaps are implemented as complete binary trees.

In a complete binary tree:

each level is filled up before another level is added, and
the bottom tier is filled in from left to right.

As we'll see, this allows us to efficiently store our heap as a list.

In a heap, every node is smaller than its children.

The diagram depicts comparing the first level of the diagram with the lower level.

The diagram depicts comparing the node 5 with the lower level.

The diagram depicts comparing the node 2 with the lower level.

The diagram depicts comparing the node 16 with the lowest level.

Inserting a new item

Add the item to the bottom of the tree.
Compare the item with its parent. If the new item is smaller, swap the two.
Continue comparing and swapping, allowing the new item to "bubble up" until the it's larger than its parent.

Because our heap is built on a complete binary tree, we know it's also balanced. Which means the height of the tree is \lg{n}. So we'll do at most \lg{n} of these swaps, giving us a total time cost of .

Removing the smallest item

Easy—it's right there at the top:

Now, we have to shuffle some things around to make this a valid heap again.

Take the bottom level's right-most item and move it to the top, to fill in the hole.
Compare the item with its children.

If it's larger than either child, swap the item with the smaller of the two children.
Continue comparing and swapping, allowing the item to "bubble down" until it's smaller than its children.

As with inserting (above), we'll do at most \lg{n} of these swaps, giving us a total time cost of .

Heaps are built on lists

Complete trees and heaps are often stored as lists, one node after the other, like this:

Complete trees are often stored as dynamic arrays, one node after the other.

Using a list to store a complete binary tree is very efficient. Since there are no gaps in complete trees, there are no unused slots in the list. And, inserting a new item in the bottom right part of the tree just means appending to the list.

But how do we traverse the tree when it's a list? How do we go from a node to its left and right children? With a bit of clever indexing! See if you can come up with the formulas for a node's left child, right child, and parent. Then, check your answer.

Heapify: Transform a List Into a Heap

Say we want to make a heap out of the items in a list.

We could create a new empty heap and add in the items from the list one at a time. If the list has n elements, then this takes .

It turns out that there's a more efficient way to transform a list into a heap.

We'll take our input list and treat it like the nodes in a complete binary tree, just like we did above:

The list [8, 3, 2, 7, 9, 1, 4] maps to a complete binary tree (8; 3, 2; 7, 9, 1, 4). Nodes within a level are separated by a comma; levels are separated with semicolons.

To transform the tree into a valid heap, we'll compare each node to its children and move nodes around so that parent nodes are always smaller than their children.

This causes larger nodes to move lower in the tree, "bubbling down" to allow smaller values to reach the top.

Look familiar? This is the same bubbling down we were doing to remove items from the heap!

We'll work from the leaf-nodes at the bottom upwards. To start off, let's look at the leaves.

The leaf nodes don't have any children, so they don't need to move down at all. Great.

In the binary tree (8; 3, 2; 7, 9, 1, 4), the bottom 4 nodes (7, 9, 1, 4) correspond to the last four elements in the list [8, 3, 2, 7, 9, 1, 4].

Let's look at the nodes in the next level:

In the binary tree (8; 3, 2,; 7, 9, 1, 4), the middle level has two nodes (3, 2), which correspond to the second and third elements in the list [8, 3, 2, 7, 9, 1, 4].

We'll start with the left node (3) and its children:

The (3) node has two children: 7 and 9. In the list [8, 3, 2, 7, 9, 1, 4], node (3) is at index 1 and its children are at indices 3 and 4.

Since 3 is smaller than both 7 and 9, it's already in the right spot.

But, looking at the right node (2) and its children, since 1 is smaller than 2, we'll swap them.

The binary tree with highlighted nodes 1, 2 and 4. Nodes 1 and 2 are swapped.

Notice how we've got two small valid min-heaps. We're getting close!

The binary tree with highlighted nodes 3, 7, 9, 1, 2, 4.

Moving up, we've got an 8 at the root.

The binary tree with highlighted node 8.

Since 8 is larger than 1, 8 bubbles down, swapping places with the smaller child: 1.

The binary tree with highlighted nodes 8 and 1 which are swapped.

Then, we need to compare 8 to its two children—2 and 4. Since 8 is bigger than both of them, we swap with the smaller child, which is 2.

The binary tree with highlighted nodes 8, 2 and 4. Nodes 8 and 2 are swapped.

At this point, we've transformed the input tree into a valid min heap. Nice!

Heapify complexity

What's the time complexity of heapify'ing a list?

It's tempting to say it's . After all, we have to examine all n nodes, and a node might bubble down levels.

That's an overestimate of the amount of work though. All of the leaf nodes at the bottom of the tree won't have to move down at all. And the parents of those nodes will only move down once. In fact, there's only one node that might move down times: the root node.

Since binary heaps are based on complete binary trees, there will be n/2 nodes in the bottom level, n/4 nodes in the second-to-last level, etc. Each time we go up a level we cut the number of nodes in half.

A binary tree with 5 rows of nodes. The root node is on top, and every node has 2 children in the row below. Each row is labelled with the number of nodes in the row, which doubles from the top down: 1, 2, 4, 8, 16.

So, we'll move n/2 nodes on the bottom level 0 times. The n/4 nodes one level up move at most 1 time. Then, n/8 nodes move at most 2 times. And so on, until we get to the root node, which moves \lg(n) times.

Adding this all up, we've got:

0 * \frac{n}{2} + 1 * \frac{n}{4} + 2 * \frac{n}{8} + 3 * \frac{n}{16} + \ldots

Alternatively, this can be expressed as a summation:

n * \sum \frac{i}{2^{i + 1}}

The sum is a geometric series that converges to 1/2. (Take our word for it—the arithmetic to prove this gets a bit hairy.) Then, multiplying by n, we have n/2. That's .

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!

Heap