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 minheap has the smallest value at the top. A maxheap has the largest value at the top. We'll describe minheaps here, but the implementation for maxheaps 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 highestpriority 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.
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 rightmost 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:
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:
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 leafnodes 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.
Let's look at the nodes in the next level:
We'll start with the left node (3) and its children:
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.
Notice how we've got two small valid minheaps. We're getting close!
Moving up, we've got an 8 at the root.
Since 8 is larger than 1, 8 bubbles down, swapping places with the smaller child: 1.
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.
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 secondtolast level, etc. Each time we go up a level we cut the number of nodes in half.
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:
Alternatively, this can be expressed as a summation:
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 7day 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. Oneclick unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!