What Is a Binary Heap? Array Layout, Insert and Remove

What is a binary heap? It is a tree of values, stored in a plain array, that keeps the smallest value (or the largest) at the front. You can read that value at once, and you can add or remove values quickly. That makes it the usual tool behind a priority queue, where you always want the next most important item.

This guide gives the two rules of a heap, walks through insert and remove, and then looks at a real route search in Tank City Zero Day. That game does not use a heap, and why is a good way to see what a heap can and cannot do.

What is a binary heap?

A binary heap is a binary tree, which means every node has at most two children. It follows two rules, one about its shape and one about the order of its values. Together they put the most important item at the top. J. W. J. Williams introduced it in 1964 for heapsort, and it is a common way to build a priority queue (Wikipedia on the binary heap).

The two rules of a heap: shape and order

Shape rule. The tree is complete. Every level is full, except possibly the last, and the last level fills from left to right with no gaps. This keeps the tree short and balanced.

Heap order rule. Each node is compared only with its own children. In a min heap, a parent is never larger than its children. That is all. Siblings have no order between them, and a node low in one branch can be smaller than a node higher up in another branch.

So a heap is not sorted. It is only partly ordered, and that is why it is cheap to keep in order.

Min heap vs max heap

The only difference is the direction of the order rule.

• In a min heap, each parent is less than or equal to its children, so the smallest value is at the root.
• In a max heap, each parent is greater than or equal to its children, so the largest value is at the root.

The code is the same apart from one comparison.

How a binary heap is stored in an array

Because the tree is complete, it has no gaps, so you do not need node objects or pointers. Lay the tree out in an array, level by level, left to right. With zero-based indexes, for a node at index i:

• Its left child is at 2*i + 1.
• Its right child is at 2*i + 2.
• Its parent is at (i - 1) / 2, rounded down.

The array [1, 3, 8, 5] is a tree with 1 at the root. Its children are 3 (index 1) and 8 (index 2), and 3 has one child, 5 (index 3).

The same heap twice: as a tree, and as the array that stores it.

How insert works (sift up)

To insert a value, put it at the end of the array. That keeps the shape rule true. Then fix the order rule by moving the new value up while it is smaller than its parent. This step is called sift up, and some books call it bubble up.

Insert 5, 3, 8, then 1 into an empty min heap.

1. Insert 5. The array is [5].
2. Insert 3. Append it to get [5, 3]. Its parent is 5, which is larger, so swap to get [3, 5].
3. Insert 8. Append it to get [3, 5, 8]. Its parent is 3, which is smaller, so stop.
4. Insert 1. Append it to get [3, 5, 8, 1]. Its parent (index 1) is 5, so swap to get [3, 1, 8, 5]. Its new parent (index 0) is 3, so swap again to get [1, 3, 8, 5]. It is at the root, so stop.

How remove works (sift down)

Removing the smallest value, the root, is the usual operation. Taking it out leaves a hole, so move the last item of the array into the root. That keeps the shape rule true. Then fix the order rule by moving that item down: at each step compare it with its two children, and swap it with the smaller child while that child is smaller than the item. This is sift down.

Start from [1, 3, 8, 5] and remove the minimum.

1. Take out 1. Move the last item, 5, to the root and shorten the array to get [5, 3, 8].
2. The children of the root are 3 and 8. The smaller is 3, and 3 is less than 5, so swap to get [3, 5, 8].
3. The item 5 has no children now, so stop.

The next removals return 3, then 5, then 8. Remove everything from a heap and the values come out in sorted order, which is the idea behind heapsort.

A common bug is comparing with the wrong child. In a min heap you must pick the smaller one, or the order rule breaks.

Time cost and where heaps are used

A complete binary tree with n items is about log base 2 of n levels tall, so a heap of one million items is only about 20 levels tall. Insert and remove each walk along one path, so each takes O(log n) time.

• Peek at the minimum: O(1), because it is the first array item.
• Insert: O(log n).
• Remove the minimum: O(log n).
• Build a heap from n existing items: O(n), using Floyd's method: start at the lowest level and sift each subtree's root down, working upward.

A heap has no order between branches, so looking for an arbitrary value means checking items one by one. It is built for "the best item next", and that shows up in task schedulers that run the highest priority job first, in shortest path search, in finding the top few items in a stream of data, and in heapsort.

A worked example: the route search in Tank City Zero Day

Tank City Zero Day, the second game on Tank City Reboot, needs "the closest item next" every time it plans where enemies walk. The arena is a grid of 25 by 25 cells. The game works out, for every cell, the cheapest distance to a goal such as your tank or the cells beside the core. A step costs 1, and a step onto firewall costs 4, because the firewall has to be shot through first. Silicon, coolant and the core cannot be stood on, so the search skips them. This is Dijkstra's algorithm, which our guide to Dijkstra's algorithm explains. Each turn it must take the unfinished cell with the lowest distance so far, and that is a priority queue job.

Here is the part that surprises people: the game does not use a heap for it. In its code, the open cells sit in a SortedSet of distance and cell pairs, and each turn the code takes the set's smallest pair and removes it. Microsoft's documentation describes that type as a collection kept in sorted order. A binary heap could do the same job: push each cell with its distance, pop the lowest, and look at its neighbours.

There is one difference. When the search finds a shorter route to a cell that is already waiting, the game removes that cell's old entry from the set and adds the new one. A plain heap cannot take an item out of the middle cheaply, so with a heap you would leave the old entry in and skip stale entries as they come out. The game has a line for that too: it skips any popped entry whose distance is larger than the one stored for the cell. With the set, that line is only a safety check. With a heap it would be essential.

You can watch the result in Tank City Zero Day: the enemy map toward your tank is rebuilt every 0.3 seconds, and the map toward the core every 0.2 seconds at most, when walls change. If you have read about breadth-first search, this is the version for steps with different costs: a plain queue is enough when every step costs 1, but once a firewall step costs 4 you need a priority queue.

Binary heap vs other structures

• Sorted array. Peeking at the smallest is cheap, but inserting means shifting items, which is O(n).
• Unsorted array. Insert is O(1), but finding the minimum is O(n).
• Sorted set or balanced tree. It gives you the minimum, lets you search for any value, and lets you walk items in order. It costs more memory and code than a heap, which fits in one array.

Pick a heap when you only need the top item, and a sorted structure when you also need to look things up or take items out of the middle.

Frequently asked questions

Is a binary heap the same as a binary search tree?

No. A binary search tree orders its left and right subtrees, so you can search it. A heap only orders each parent against its children, so it is good for the minimum or maximum and poor for searching.

Why store a heap in an array?

The complete shape leaves no gaps, so parent and child positions follow simple index formulas. You skip pointers and keep the data together in memory.

Is a binary heap the same as the memory heap?

No. They share a name but are unrelated. The memory heap is the area where a program allocates objects, and a binary heap is a data structure.

Get started

Write a min heap yourself in your favourite language, with sift up and sift down, and test it until every removal comes out in order.

For a feel of how a search for the cheapest route plays out on screen, Play Tank City Reboot: it is free, plays in your browser on a computer or a phone, and needs no account.