This chapter will introduce heaps. A heap is an important data structure that returns the highest or lowest element in O(1) time. This chapter will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
Understanding Heaps
A heap is a type of tree-like data structure in which the parent is bigger than its children (if max-heap) or smaller than its children (if min-heap). This property of the heap makes it useful for sorting data.
Heaps, unlike other tree data structures, use an array to store data instead of having pointers to their children. A heap node’s children’s positions (indices) in the array can be calculated easily. This is because the parent-child relationship is easily defined with a heap.
There are many types of heaps that have different numbers of children. In this chapter, only binary heaps will be considered. Since a heap uses an array to store the data, the indices of the array define the order/height of each element. A binary heap can be built by placing the first array element as the root and then filling each left and right element in order.
For example, for the heap shown in Figure 16-1, the array would look like this: [2, 4, 23, 12, 13].
Figure 16-1
Heap indices
There are two types of binary heaps: max-heap and min-heap. In max-heap, the root node has the highest value, and each node’s value is greater than its children. In min-heap, the root node has the lowest value, and each node’s value is smaller than its children.
Heaps can store any values of any type: strings, integer, and even custom classes. As covered in Chapters 3 and 4, strings and integer value comparisons are handled natively by JavaScript (e.g., 9 is greater than 1, z is greater than a). However, for custom classes, the developer needs to implement a way to compare two classes. This chapter will look at heaps that store integer values only.
Max-Heap
A max-heap is a heap where the parent is always greater than any of its children (see Figure 16-2).
Figure 16-2
Max-heap
Here is the array for the max-heap shown in Figure 16-2: [100, 19, 36, 17, 3, 25, 1, 2, 7].
Min-Heap
A min-heap is a heap where the parent is always smaller than any of its children (see Figure 16-3).
Figure 16-3
Min-heap
Here is the array for the max-heap shown in Figure 16-3: [1, 2, 3, 17, 19, 36, 7, 25, 100].
Binary Heap Array Index Structure
For a binary heap, an array is used to represent the heap by using the following indices, where N is the index of the node:
Node Index
(itself) N
Parent (N-1) / 2
Left Child (N*2) + 1
Right Child (N*2) + 2
Figure 16-4 illustrates this familial relationship using indices.
Figure 16-4
Heap relationship
Let’s first define a generic Heap class. An array will be used to store all the values using the index structure described earlier. The following heap class implements helper functions that retrieve the parent node, the left child, and the right child. The following code block has a peek function that returns the maximum value for a max-heap and the minimum value for a min-heap.
The size function is another helper that returns the size (number of elements) of the heap.
Percolation: Bubbling Up and Down
When elements are added or removed, the structure of the heap must remain (the node being greater than its children for a max-heap or smaller than its children for a min-heap).
This requires items to swap and “bubble up” to the top of the heap. Similar to bubbling up, some items need to “bubble down” to their rightful position in order to keep the structure of the heap. Percolation takes O(log2(n)) in time.
Let’s step through a min-heap example and insert the following values into the min-heap in this order: 12, 2, 23, 4, 13. Here are the steps:
Here is the array content for this heap: [2, 4, 23, 12, 13].
Implementing Percolation
To implement the “bubbling up and down” of percolation, swap until the min-heap structure is formed with the minimum element on the top. For bubbling down, swap the top element (first in the array) with one of its children if that child is smaller. Likewise, for bubbling up, swap the new element with its parent if the parent is greater than the new element.
1 function MinHeap() {
2 this.items = [];
3 }
4 MinHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
5 MinHeap.prototype.bubbleDown = function() {
6 var index = 0;
7 while (this.leftChild(index) && this.leftChild(index) < this.items[index]) {
21 while (this.parent(index) && this.parent(index) > this.items[index]) {
22 this.swap(this.parentIndex(index), index);
23 index = this.parentIndex(index);
24 }
25 }
A max-heap implementation differs only in the comparators. For bubbling down, the max-heap node swaps with one of its children if the child is greater. Likewise, for bubbling up, the newest node swaps with its parent if its parent is smaller than the new node.
Max-Heap Example
Let’s build a max-heap now with the same values as the one used in the previous min-heap example by inserting the following values in the order: 12, 2, 23, 4, 13.
1.
Insert the first node, which is 12 (Figure 16-12).
Because of the max-heap structure, 13 and 4 swap positions (Figure 16-19).
Figure 16-19
Percolation restores the max-heap structure
Here is the array content for this heap: [23, 13, 12, 2, 4].
Min-Heap Complete Implementation
Putting all the functions defined together and inheriting Heap’s functions, the complete implementation and example of min-heap is shown next. The add and poll functions were added. add simply adds a new element to the heap, but bubbleUp ensures that this element in the min-heap satisfies the order. poll removes the minimum element (the root) from the heap and calls bubbleDown to keep the min-heap order.
1 function MinHeap() {
2 this.items = [];
3 }
4 MinHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
22 if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
23 smallerIndex = this.rightChildrenIndex(index);
24 }
25 this.swap(smallerIndex, index);
26 index = smallerIndex;
27 }
28 }
29
30 MinHeap.prototype.bubbleUp = function() {
31 var index = this.items.length - 1;
32 while (this.parent(index) && this.parent(index) > this.items[index]) {
33 this.swap(this.parentIndex(index), index);
34 index = this.parentIndex(index);
35 }
36 }
37
38 var mh1 = new MinHeap();
39 mh1.add(1);
40 mh1.add(10);
41 mh1.add(5);
42 mh1.add(100);
43 mh1.add(8);
44
45 console.log(mh1.poll()); // 1
46 console.log(mh1.poll()); // 5
47 console.log(mh1.poll()); // 8
48 console.log(mh1.poll()); // 10
49 console.log(mh1.poll()); // 100
Max-Heap Complete Implementation
As previously discussed, the only difference between the min-heap and max-heap implementations is the comparator in bubbleDown and bubbleUp. With the same elements added as the previous example, meaning (1, 10, 5, 100, 8), the max-heap returns the highest elements when poll is called.
1 function MaxHeap() {
2 this.items = [];
3 }
4 MaxHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
17 if (this.rightChild(index) && this.rightChild(index) > this.items[bigger\Index])
18 {
19 biggerIndex = this.rightChildrenIndex(index);
20 }
21 this.swap(biggerIndex, index);
22 index = biggerIndex;
23 }
24 }
25
26 MaxHeap.prototype.bubbleUp = function() {
27 var index = this.items.length - 1;
28 while (this.parent(index) && this.parent(index) < this.items[index]) {
29 this.swap(this.parentIndex(index), index);
30 index = this.parentIndex(index);
31 }
32 }
33
34 var mh2 = new MaxHeap();
35 mh2.add(1);
36 mh2.add(10);
37 mh2.add(5);
38 mh2.add(100);
39 mh2.add(8);
40
41 console.log(mh2.poll()); // 100
42 console.log(mh2.poll()); // 10
43 console.log(mh2.poll()); // 8
44 console.log(mh2.poll()); // 5
45 console.log(mh2.poll()); // 1
Heap Sort
Now that heap classes have been created, sorting with a heap is fairly straightforward. To get a sorted array, simply call .pop() on the heap until it is empty and store the stored popped objects. This is as known as a heap sort. Since percolation takes O(log2(n)), and sorting must pop n number of elements, the time complexity for a heap sort is O(nlog2(n)), like quicksort and mergesort.
In this section, we will first do an ascending sort implemented using a min-heap and then a descending sort implemented using a max-heap.
Ascending-Order Sort (Min-Heap)
Figure 16-20 shows the min-heap when all the items have been added to the min-heap, and Figures 16-21 to 16-23 show the heap restructuring as items are popped. Finally, when it is empty, the sort is complete.
Figure 16-20
Min-heap sort after all items added
Figure 16-21
Min-heap sort: popping 2 out
Figure 16-22
Min-heap sort: popping 4 out
Figure 16-23
Min-heap sort: popping 12 out
1 var minHeapExample = new MinHeap();
2 minHeapExample.add(12);
3 minHeapExample.add(2);
4 minHeapExample.add(23);
5 minHeapExample.add(4);
6 minHeapExample.add(13);
7 minHeapExample.items; // [2, 4, 23, 12, 13]
8
9 console.log(minHeapExample.poll()); // 2
10 console.log(minHeapExample.poll()); // 4
11 console.log(minHeapExample.poll()); // 12
12 console.log(minHeapExample.poll()); // 13
13 console.log(minHeapExample.poll()); // 23
The last node (where 13 used to be) is removed, and then 13 is placed on the top. Through the percolation process, 13 moves down to after the left child of 12 since it’s bigger than both 4 and 13.
Descending-Order Sort (Max-Heap)
Figure 16-24 shows the max-heap when all the items have been added to the min-heap, and Figures 16-25 through 16-27 show the max-heap restructuring as items are popped. Finally, when it is empty, the sort is complete.
Figure 16-24
Max-heap sort after all items are added
Figure 16-25
Max sort: popping 23 out
Figure 16-26
Max sort: popping 13 out
Figure 16-27
Max sort: popping 12 out
1 var maxHeapExample = new MaxHeap();
2 maxHeapExample.add(12);
3 maxHeapExample.add(2);
4 maxHeapExample.add(23);
5 maxHeapExample.add(4);
6 maxHeapExample.add(13);
7 maxHeapExample.items; // [23, 13, 12, 2, 4]
8
9 console.log(maxHeapExample.poll()); // 23
10 console.log(maxHeapExample.poll()); // 13
11 console.log(maxHeapExample.poll()); // 12
12 console.log(maxHeapExample.poll()); // 2
13 console.log(maxHeapExample.poll()); // 4
Summary
A heap is a tree-like data structure represented using arrays. To get the parent, left child, and right child of a tree’s node, you can use the index formula in Table 16-1.
Table 16-1
HeapNode Index Summary
Node
Index
(self)
N
Parent
(N-1) / 2
Left child
(N*2) + 1
Right child
(N*2) + 2
Heaps maintain their structure via percolation; when a node is inserted, it “bubbles up” by repeatedly swapping with elements until the proper heap structure is achieved. For a min-heap, this means the lowest-valued node at the root. For a max-heap, this means the highest-valued node at the root. Heaps work fundamentally by percolation, which allows deletion and insertion in O(log2(n)) time, as summarized in Table 16-2.
Table 16-2
HeapOperations Summary
Operation
Time Complexity
Deletion (leads to “bubble down”)
O(log2(n))
Insertion (leads to “bubble up”)
O(log2(n))
Heap sort
O(n log2(n))
Exercises
You can find all the code for the exercises on GitHub.1
KEEP TRACK OF MEDIAN IN STREAM OF NUMBERS
Since this question is in this chapter, that’s already a big hint for approaching it. In theory, the solution is fairly simple. Have one min-heap and one max-heap, and then retrieving the median takes only O(1).
For example, let’s have a stream of the following integers: 12, 2, 23, 4, 13.
Median, when 12 is inserted, is 12 since that’s the only element. When 2 is inserted, there is an even number of items: 2 and 12. Hence, the median is its arithmetic mean, 7 ((12+2)/2). When 23 is inserted, the median is 12. Finally, when 13 is inserted, the median is 12.5, the average of two middle terms (12 and 13).
This problem has been explored before in Chapter 10 using quicksort’s helper function. Another way to do it is to use a heap. Simply add the elements into a heap and pop it kth times. By definition of min-heaps, this returns the kth smallest value in the array.
1 var array1 = [12, 3, 13, 4, 2, 40, 23]
2
3 function getKthSmallestElement(array, k) {
4 var minH = new MinHeap();
5 for (var i = 0, arrayLength = array.length; i < arrayLength; i++) {
6 minH.add(array[i]);
7 }
8 for (var i = 1; i < k; i++) {
9 minH.poll();
10 }
11 return minH.poll();
12 }
13 getKthSmallestElement(array1, 2); // 3
14 getKthSmallestElement(array1, 1); // 2
15 getKthSmallestElement(array1, 7); // 40
FIND THE KTH LARGEST VALUE IN AN ARRAY
This is the same idea from before just with max-heap.
1 var array1 = [12,3,13,4,2,40,23];
2
3 function getKthBiggestElement(array, k) {
4 var maxH = new MaxHeap();
5 for (var i=0, arrayLength = array.length; i<arrayLength; i++) {
6 maxH.push(array[i]);
7 }
8 for (var i=1; i<k; i++) {
9 maxH.pop();
10 }
11 return maxH.pop();
12 }
13 getKthBiggestElement(array1,2); // 23
14 getKthBiggestElement(array1,1); // 40
15 getKthBiggestElement(array1,7); // 2
Time Complexity: O(klog2(n))
Here, n is the size of the array since each .pop costs O(log2(n)), which has to be done k times.
