Objectives

By the end of this chapter, you should be able to:

• Describe what a binary heap is and how it is commonly used
• Compare and contrast min and max heaps and how insertion and deletion works

Introduction to Binary Heaps

In addition to binary search trees, there is a similar data structure called a binary heap which shares some characteristics to binary search trees, but is a bit different in its implementation, which makes it a better data structure for some operations, but not others. With binary heaps, there are two common implementations, a max heap (the higher nodes bubble up to the root) and a min heap (the lower nodes bubble up to the root)

A binary heap can be implemented in two different ways, either as a tree or as an array, but let's first define the rules for a binary heap.

• each node can only have at most two children (similar to a binary search tree)
• when a node is added, you always start at the root and then keep adding, top to bottom, left to right. This is unlike a binary search tree. In a binary search tree the spot where you add a node depends on the value, but in a binary heap, the spot in which you add is always in order from top to bottom, left to right. Let's take a look at a one kind of binary heap - a max heap

Max Heaps

Let's take a look at a max-heap:

Notice that the larger values are closer to the root, with the largest value being the root. Remember the order of a heap, everything must be from top to bottom and then left to right so all that matters in terms of the max value is that the parent node is always greater than the child node. This is not like a binary search tree where all values less than a parent node go on the left. With a binary heap we build the data structure starting from the top and going to the bottom and then left to right. If another node were to be inserted, it would be to the left of the node with a values of 3.

Min Heaps

Let's take a look at a min-heap:

Notice that the smaller values are closer to the root, with the smallest value being the root. If another node were to be inserted, it would be to the left of 19

Insertion

Let's now take a look at how to insert a node into a binary heap. For this example we will be using a max heap. Let's first examine the operations necessary for correctly inserting a node in a max-heap.

1. Add the element to the heap (work your way from top to bottom, then left to right). We do not worry about comparing values and trying to insert it at the correct position based on its value, we only need to place it in the correct spot to satisfy the rules of a heap (nodes are placed top to bottom, then left to right).
2. Once the element is placed at the last spot in the heap (top to bottom, left to right), compare the element with its parent. If the element is less than its parent, it is in the correct order and you are done. If the element is greater than its parent, you swap the placement of the parent node and the element. Keep repeating this process until the element you are adding has a parent that is greater than itself or the element you are adding is at the root. This can be done iteratively or recursively.

You can read more about insertion here and you can watch an excellent video on insertion here

Deletion

Let's now take a look at how to remove a node into a binary heap. For this example we will be using a max heap. While we could remove nodes from anywhere in a heap, removal is commonly done through removing the root node (the highest value in a max heap or the lowest value in a min heap). Here is how it works with a max-heap:

1. Replace the root of the heap with the last element on the last level (all the way on the bottom, the last node remaining going from left to right). Once again, we are not worried about comparing values, we just need to move another node to where the root node was (since it is now removed). We will compare values later.
2. Compare the new root node with its children, if it is greater than both of its children, keep it there. If it is less than its children, pick the higher of the children and swap the position of the new root with the child. Keep repeating this process until the node which has become the root is in the correct place (has a parent with a greater value).

You can read more about deletion here and you can watch an excellent video on deletion here

Array implementation

So far we have seen how to visualize a binary heap using a tree, but we can also implement it with an array. Arrays are how binary heaps are commonly implemented in JavaScript for common use cases like heapsort and priority queues. When we build a heap using an array, it is important to understand the placement of parents relative to their children. Here is the rule with regards to that:

For a parent at index n:
- its left child will be at index 2n + 1
- its right child will be at index 2n + 2

For a child node at index n
- its parent node will be at index Math.floor( (n-1) / 2 )

Here is what a min-heap with an array representation would look like:

Using the index values in the array, see how the 2n+1 and 2n+2 rules apply as well as finding a parent index from a child index. These rules are essential to understand for inserting and deleting when using an array to represent a binary heap.

You can watch an excellent video on an array implementation here

Use Cases

Binary Heaps are commonly used for the following (as well as quite a few other things):

heapsort - Heapsort is a useful in-place (O(1) space complexity) sorting algorithm that has an average performance of O(n log(n)). It requires building a heap and then swapping values to sort. You can read more about heapsort here and see a good visualization here.

priority queue - We previously have seen queues which allow for O(1) insertion and deletion and a more advanced implementation of a queue is one that can re-order itself when a new element is enqueued. The elements in the queue are re-ordered in terms of their priority, which is why this is called a priority queue. Priority queues are easily implemented using min or max heaps to manage the priority and ordering of the queue.

min-max-heap - we have seen min and max heaps, but there is also another data structure called a min-max heap which is a combination of min and max heaps and are frequently used to implement double-ended priority queues. You can read more about them here.

Performance Characteristics

Binary heaps have impressive performance characteristics for deletion and insertion, but they are not as efficient as binary search trees for searching since each node must be visited. The space complexity for a binary heap is O(n) similar to binary search trees.

Additional Resources

https://en.wikipedia.org/wiki/Binary_heap

http://eloquentjavascript.net/1st_edition/appendix2.html