Arrays as Heaps
Because finding the last node is so critical to the heap’s operations, and because we want to make sure that finding the last node is efficient, heaps are usually implemented using arrays.
While until now we always assumed that every tree consists of independent nodes connected to each other with links (just like a linked list), you’ll now see that we can also use an array to implement a heap. The heap itself can be an abstract data type that really uses an array under the hood.
The shows how an array is used to store the values of a heap.
The way this works is that we assign each node to an index within the array. In the previous diagram, the index of each node is found in a square below the node. If you look carefully, you’ll see that we assign the index of each node according to a specific pattern.
The root node is always stored at index 0. We then move down a level and go from left to right, assigning each node to the next available index in the array. So on the second level, the left node (88) becomes index 1, and the right node (25) becomes index 2. When we reach the end of a level, we move down to the next level and repeat this pattern.
Now, the reason why we’re using an array to implement the heap is because it solves the problem of the last node. How?
When we implement the heap in this fashion, the last node will always be the final element of the array. Since we move top-down and left to right when assigning each value to the array, the last node will always be the final value in the array. In the previous example, you can see that the 3, which is the last node, is the last value in the array.
Because the last node will always be found at the end of the array, it becomes trivial to find the last node: we just need to access the final element. Additionally, when we insert a new node into the heap, we do so at the end of the array to make it the last node.
Before we get into the other details of how an array-based heap works, we can already begin to code its basic structure. Here’s the beginning of our heap implementation in Python:
| | class Heap: |
| | def __init__(self): |
| | self.data = [] |
| | |
| | def root_node(self): |
| | return self.data[0] |
| | |
| | def last_node(self): |
| | return self.data[-1] |
As you can see, we initialize the heap as an empty array. We have a root_node method, which returns the first item of this array, and we also have a last_node method that returns the last value of this array.
Traversing an Array-Based Heap
As you’ve seen, the heap’s insertion and deletion algorithms require us to be able to trickle our way through the heap. Trickling, in turn, requires us to be able to traverse the heap by accessing a node’s parent or children. But how do we move from node to node when all the values are merely stored in an array? Traversing a heap would have been straightforward if we could have simply followed each node’s links. But now that the heap is an array under the hood, how do we know which nodes are connected to each other?
This has an interesting solution. It turns out that when we assign the indexes of the heap’s nodes according to the pattern described earlier, the following traits of a heap are always true:
- To find the left child of any node, we can use the formula (index * 2) + 1.
- To find the right child of any node, we can use the formula (index * 2) + 2.
Take another look at the previous diagram and focus on the 16, which is at index 4. To find its left child, we multiply its index (4) by 2 and add 1, which yields 9. This means that index 9 is the left child of the node at index 4.
Similarly, to find the right child of index 4, we multiply the 4 by 2 and add 2, which yields 10. This means that index 10 is the right child of index 4.
Because these formulas always work, we’re able to treat our array as a tree.
Let’s add these two methods to our Heap class:
| | def left_child_index(self, index): |
| | return (index * 2) + 1 |
| | |
| | def right_child_index(self, index): |
| | return (index * 2) + 2 |
Each of these methods accepts an index within the array and returns the left or right child index, respectively.
Here’s another important trait of array-based heaps:
- To find a node’s parent, we can use the formula (index - 1) // 2.
Note that this formula uses floor division, meaning we throw away any numbers beyond the decimal point. For example, 3 // 2 returns 1, rather than the more accurate 1.5.
Again, in our example heap, focus on index 4. If we take that index, subtract 1, and then divide by 2, we get 1. And as you can see in the diagram, the parent of the node at index 4 is found at index 1.
So now we can add another method to our Heap class:
| | def parent_index(self, index): |
| | return (index - 1) // 2 |
This method accepts an index and calculates the index of its parent node.
Code Implementation: Heap Insertion
Now that we have the essential elements of our Heap in place, let’s implement the insertion algorithm:
| | def insert(self, value): |
| | self.data.append(value) |
| | new_node_index = len(self.data) - 1 |
| | |
| | while (new_node_index > 0 and |
| | (self.data[new_node_index] |
| | > self.data[self.parent_index(new_node_index)])): |
| | |
| | parent_index = self.parent_index(new_node_index) |
| | self.data[parent_index], self.data[new_node_index] = \ |
| | self.data[new_node_index], self.data[parent_index] |
| | |
| | new_node_index = parent_index |
As usual, let’s break this thing down.
Our insert method accepts the value we’re inserting into our heap. The first thing we do is make this new value the last node by adding it to the very end of the array:
| | self.data.append(value) |
Next, we keep track of the index of the new node, as we’ll need it later. Right now, the index is the last index in the array:
| | new_node_index = len(self.data) - 1 |
Next, we trickle up the new node to its proper place using a while loop:
| | while (new_node_index > 0 and |
| | (self.data[new_node_index] |
| | > self.data[self.parent_index(new_node_index)])): |
This loop runs as long as two conditions are met. The main condition is that the new node is greater than its parent node. We also make a condition that the new node must have an index greater than 0, as funny things can happen if we try to compare the root node with its nonexistent parent.
Each time this loop runs, we swap the new node with its parent node, since the new node is currently greater than the parent:
| | parent_index = self.parent_index(new_node_index) |
| | self.data[parent_index], self.data[new_node_index] = \ |
| | self.data[new_node_index], self.data[parent_index] |
We also then update the index of the new node appropriately:
| | new_node_index = parent_index |
Since this loop only runs while the new node is greater than its parent, the loop ends once the new node is in its proper place.
Code Implementation: Heap Deletion
We’ll next look at an implementation of deleting an item from a heap. We named the method pop, since the term pop implies a focus on returning the deleted value to be used by other code, such as in a priority queue (as we’ll see soon). We’re not merely trying to eliminate the root value; we also want to pass that value along to other code to be processed.
The main method is the pop method, but to make the code simpler, we’ve created two helper methods, has_greater_child and find_larger_child_index.
Here goes:
| | def pop(self): |
| | value_to_delete = self.root_node() |
| | self.data[0] = self.data.pop() |
| | trickle_node_index = 0 |
| | |
| | while self.has_greater_child(trickle_node_index): |
| | larger_child_index = self.find_larger_child_index(trickle_node_index) |
| | |
| | self.data[trickle_node_index], self.data[larger_child_index] = \ |
| | self.data[larger_child_index], self.data[trickle_node_index] |
| | |
| | trickle_node_index = larger_child_index |
| | |
| | return value_to_delete |
| | |
| | def has_greater_child(self, index): |
| | return ((self.left_child_index(index) <= len(self.data) and |
| | self.data[self.left_child_index(index)] > self.data[index]) |
| | or |
| | (self.right_child_index(index) <= len(self.data) and |
| | self.data[self.right_child_index(index)] > self.data[index])) |
| | |
| | def find_larger_child_index(self, index): |
| | if not self.data[self.right_child_index(index)]: |
| | return self.left_child_index(index) |
| | |
| | if (self.data[self.right_child_index(index)] |
| | > self.data[self.left_child_index(index)]): |
| | return self.right_child_index(index) |
| | else: |
| | return self.left_child_index(index) |
Let’s first dive into the pop method.
The pop method doesn’t accept any arguments, since the only node we ever delete is the root node. Here’s how the method works.
First, we save the value we’re going to delete so we can return it at the end of the function:
| | value_to_delete = self.root_node() |
Next, we remove the last value from the array and make it the first value:
| | self.data[0] = self.data.pop() |
This simple line effectively deletes the original root node, as we’re overwriting the root node’s value with the last node’s value.
Next, we need to trickle the new root node down to its proper place. We called this the trickle node earlier, and our code reflects this.
Before we start the actual trickling, we keep track of the trickle node’s index, as we’ll need it later. Currently, the trickle node is at index 0:
| | trickle_node_index = 0 |
We then use a while loop to execute the trickle-down algorithm. The loop runs as long as the trickle node has any children that are greater than it:
| | while self.has_greater_child(trickle_node_index): |
This line uses the has_greater_child method, which returns whether a given node has any children who are greater than that node.
Within this loop, we first find the index of the greater of the trickle node’s children:
| | larger_child_index = self.find_larger_child_index(trickle_node_index) |
This line uses the method find_larger_child_index, which returns the index of the trickle node’s greater child. We store this index in a variable called larger_child_index.
Next, we swap the trickle node with its greater child:
| | self.data[trickle_node_index], self.data[larger_child_index] = \ |
| | self.data[larger_child_index], self.data[trickle_node_index] |
We update the index of the trickle node, which will be the index it was just swapped with:
| | trickle_node_index = larger_child_index |
Finally, we return the value of the node we deleted from the heap:
| | return value_to_delete |
Alternate Heap Implementations
Our heap implementation is now complete. It’s worth noting that while we did use an array to implement the heap under the hood, it is possible to implement a heap using linked nodes as well. (This alternative implementation uses a different trick to solve the problem of the last node, one that involves binary numbers.)
However, the array implementation is the more common approach, so that’s what I presented here. It’s also interesting to see how an array can be used to implement a tree.
Indeed, it’s possible to use an array to implement any sort of binary tree, such as the binary search tree from the previous chapter. However, the heap is the first case of a binary tree where an array implementation provides an advantage, as it helps us find the last node easily.
