At this point we have a good idea of how a priority queue should be used and its internal representation. It’s about time we delve into the details of the implementation for a heap.
Before we go, let’s once again take a look at our API:
class Heap {
top()
peek()
insert(element, priority)
remove(element)
update(element, newPriority)
}
These are just the public methods defining the API of our class.
But first things first. We will assume, hereafter, that we store all the (element, priority) tuples added to the heap in an array named pairs, as shown in listing 2.1.
Listing 2.1 The DHeap class properties
class DHeap
#type Array[Pair]
pairs
function DHeap(pairs=[])
This is the first time we see a code snippet in this book. It might be a good chance for you to review appendix A, where we explain the syntax used. For instance, if we have a variable p holding such a tuple, we embrace a specific syntax for destructured assignment of its fields into two variables:
(element, priority) ← p
We also assume that the tuple’s fields are named, so that we can access, in turn, p.element and p.priority, or create a tuple p with this syntax:
p ← (element=’x’, priority=1)
In many figures in this section, we will only show an element’s priorities or, to see it in another way, we assume that elements and priorities are the same. This is just for the sake of space and clarity in diagrams, but it also highlights an important characteristic of heaps: in all their methods, we only need to access and move priorities. This can be important when elements are large objects, especially if they are so large that they won’t fit in cache/memory or for any reason they are stored on disk; then the concrete implementation can just store and access a reference to the elements and its priority.
Now, before delving into the API methods, we need to define two helper functions that will be used to reinstate the heap properties whenever a change is performed. The possible changes for a heap are
- Adding a new element to the heap
- Removing the top element of the heap
- Updating an element’s priority
Any of these operations can cause a heap element to have higher priority than its parent or a lower priority than (one of) its children.
1. BubbleUp
When an element has a higher priority than its parent, it is necessary to call the bubbleUp method, as shown in listing 2.2. Figure 2.6 shows an example based on our task management tool: the priority of the element at index 7 is higher than its parent (at index 2) and thus these two elements need to be swapped.
As listing 2.2 shows, we keep swapping elements until either current element gets assigned to the root (line #3), or its priority is lower than its next ancestor (line #6-#9). This means that each call to this method can involve at most logD (n) comparisons and exchanges, because it’s upper-bounded by the height of the heap.
Remember we are implementing a max-heap, so higher numbers mean higher priority. Then, as shown in figure 2.6 (A), the element at index [7] is out of place, because its parent, “Optional form field blocked . . . ” at index [2], has priority 8 < 9.
At this point, to fix things we need to call bubbleUp(pairs, 7). We enter the loop at line #3, because parentIndex is 7 > 0, compute the new parent’s index, which is 2, and hence the condition at line #6 is also true, so at line #7 the two elements will be swapped. After the update, the heap’s array will look like figure 2.6 (B).
At the next iteration of the loop (parentIndex is still 2 > 0, so the loop will be entered at least once more), the new values for currentIndex and parentIndex will evaluate, at lines #4-5, to 2 and 0, respectively.
Since elements’ priorities are now, in turn, 9 and 10 for child and parent, the condition at line #6 is not met anymore, and the function will break out of the loop and return.
Notice that this method, if the height of the tree is H, requires at most H swaps, because each time we swap two elements, we move one level up in the tree, toward its root.
This result is an important result, as we will see in section 2.7. Because heaps are balanced binary trees, their height is logarithmic in the number of elements.
But we can add a further improvement with just a small change. If you notice, we are repeatedly swapping the same element with its current parent; this element, the one on which bubbleUp is initially called, keeps moving toward the root. You can see in figure 2.6 that it “bubbles up,” like a soap bubble floating toward the top of the heap. Each swap requires three assignments (and the use of a temporary variable), so the naive implementation in listing 2.2 would require (at most) 3*H assignments.
While both indices, the current and the parent node’s, change at each iteration, the value of the current element is always the same.
Figure 2.7 highlights the path that such an element has to travel. In the worst case it travels up to the root, as shown in the picture, but possibly bubbling up could stop at an intermediate node. It turns out that bubbling up an element in the path P to the heap’s root is equivalent to inserting that element in the (sub)array obtained by only considering those elements in P (see figure 2.7 (B)).
Referring to figure 2.7, the first action needed is saving to a temporary variable the element X that will move up (step 1). Then, starting with its parent, we compare all elements in the path to the temporary variable and copy them over in case they have lower priority (steps 1-3). At each time, we copy the parent element over its one child that is on the path P. It’s like we filter out all the elements in the heap’s array that are not part of P: this is highlighted in 2.7 (C).
Finally, when we find an element Y along P that has higher priority than our temporary, we can copy element X from the temporary variable to the one child of Y that belongs to P (step 4).
Now, this can be done efficiently, in the same way each iteration of the insertion sort algorithm works. We initially save in a temporary variable a copy of the element to bubble up (call it X), and then check the elements on its left in the array. We “move” the elements to their right (check figure 2.7 (C)) by copying them to the next position on their left, until we find an element with a priority higher than X’s. This can be done with just (at most) H+1 assignments for a path of length H, thus saving about 66% of the assignments.
Listing 2.3 shows the improved version of the bubbleUp method. Notice how, at some point, there will momentarily be two copies of the element originally at index [3] (and later, of the element at index [1]). This is because rather than actually swapping elements, we can just overwrite the current element with its parent at each iteration (line #6) and write the element bubbling up just once at the end as the last action in the method. This works because bubbling up an element is conceptually equivalent to the inner loop of insertion sort, where we are looking for the right position to insert the current element into the path connecting it to heap’s root.
2. PushDown
The pushDown method handles the symmetric case where we need to move an element down toward the leaves of the heap, because it might be larger than (at least) one of its children. An implementation is shown in listing 2.4.
There are two differences with the “bubble up” case:
- The triggering condition—In this case, the altered node doesn’t violate invariant 3 with respect to its parent but might violate it when compared to its children. This would happen, for instance, when the root is extracted from the heap and replaced with the last leaf in the array, or when a node priority is changed by assigning it a lower priority.
- The algorithm—For every level the element we are pushing down goes through, we need to find its highest-priority child, in order to find where the element could land without violating any property.
This method’s running time, while asymptotically equivalent to bubbleUp’s, requires a slightly larger number of comparisons. In the worst case, D * logD (n), for a heap with branching factor D and containing n elements. This is also the reason why increasing the branching factor (the max number of children for each node) indefinitely is not a good idea: we’ll see this in section 2.10.
To stick to our tasks example, let’s consider the case where the root’s priority is lower than its children, shown in figure 2.8. Working on a ternary Heap, its first leaf is stored at index 4.
We call pushDown (pairs, 0) to fix the third heap’s property; helper function first- LeafIndex at line #3 will return 3 (because the element at index [7], the last one in the array, is a child of the node at index [2], which is the last internal node), and so we will enter the loop.
The children of element [0] are at positions [1], [2], and [3], and among them we’ll choose the highest priority child of the root, at line #4. It turns out to be the element <Unencrypted password on DB, 10>. Its priority is higher than current element’s, so at line #6 we will swap it with current element.
Overall, after one iteration of the while loop, we have the situation illustrated by sub-figure 2.8.B, and currentIndex is set to 1.
Therefore, when we enter the loop for the second time, at line #3 currentIndex evaluates to 1, which is still less than 3, the index of the first leaf. The children of the element at index [1] are at indices [4], [5], and [6]. Among those elements we look for the node with highest priority among the current node’s children, at line #4 in listing 2.4; it turns out it is the element at index [4], <Page loads take 2+ seconds, 7>.
Therefore, at line #5, we find out that this time, all children’s priorities are lower than the current element’s, and we break out of the loop and return without any further change.
Similar to bubbleUp, pushDown can be improved by simply keeping the current element in a temporary variable and avoiding swaps at each iteration.
Listing 2.5 shows the final improved version of the method. We encourage the reader to work our example out line by line, similar to what we have done in the previous section for bubbleUp, to have a better grasp of how it works.
Now that we have defined all the helper methods we need, we can finally implement the API methods. As a spoiler, you will notice how all the logic about priority and max- heap vs min-heap is encapsulated into bubbleUp and pushDown, so by defining these two helper methods, we greatly simplify our life whenever it comes to adapting our code to different situations.
3. Insert
Let’s start with insertion. Listing 2.6 describes the pseudocode for inserting a new (element, priority) pair into a heap.
As mentioned at the end of the previous section, the insert method can be written by leveraging our helper methods, and as such its code is valid independent of whether we use a min-heap or a max-heap and of the definition of priority.
The first two steps in listing 2.6 are self-explanatory: we are just performing some maintenance on our data model, creating a pair from the two arguments and appending it to the tail of our array. Depending on the programming language and the type of container used for pairs, we might have to manually resize it (statically dimensioned arrays) or just add the element (dynamic arrays or lists).
The last step is needed because the new pair might violate the heap’s properties we defined in section 2.5.3. In particular, its priority could be higher than its parent’s. To reinstate heap properties, we then need to “bubble it up” toward the root of the heap, until we find the right spot in the tree structure.
Insert operations, just like delete or update, or even heap’s construction, will have to make sure the heaps properties holds on completion.
Because of the compact array implementation there will be no pointers to redirect, and the structure will be guaranteed to be consistent with properties 1 (by construction) and 2 (unless you have bugs in your code, of course).
So, we have to guarantee property 3, or in other words that each node is larger (for a max-heap) than each one of its D children. To do so, as we mentioned in previous sections, we might have to push it down (on deletes, and possibly updates), or bubble it up toward the root (on insert, and updates as well), whenever heap invariants are violated.
If we go back to our task management example, we can see how insert works on a ternary max-heap. Suppose we have the initial state shown in figure 2.9 (A), describing the heap right after a call to insert(“Add exception for Superbowl”, 9.5) to add a particularly urgent task that marketing is pushing to have fixed by the end of the day. (And yes, they do cheat using fractional numbers for priority! But that’s probably not the first time you’ve seen someone changing requirements after you’ve pulled up a lot of work, is it?). After executing line #3 in listing 2.6, in fact, the list would be in this intermediate state (where heap properties are still violated).
Line #4 is then executed to reinstate heap property number 3, as we saw in section 2.6.2, and the final result is shown in figure 2.9 (B). Notice the order in which the children of the root appear in the array: siblings are not ordered, and in fact a heap doesn’t keep a total ordering on its elements like a BST would.
4. Top
Now that we have seen how to insert a new element, let’s define the top method that will extract the heap’s root and return it to the caller.
Figure 2.10 shows an example of a max-heap, highlighting the steps that are performed in listing 2.7.
The first thing we do is check that the heap is not empty. If it is, we certainly can’t extract the top element, so we need to issue an error.
The idea is that since we will remove the root of the heap, and by doing so we leave a “hole” in the array, we need to replace it with another element.
We could “promote” one of its children as the new root, as shown in listing 2.7. (One of them will certainly be the next-highest priority element; try to prove it as an exercise.)
However, we would then only move the problem to the subtree rooted at this node that we moved to the root, and then to the next level, and so on.
Instead, since we also have to shrink the array, and since it’s easier to add or remove the array’s elements from its tail, we can simply pop the last element in the array and use it to replace the root.
The caveat is that this new root might violate heap’s properties. As a matter of fact, being a leaf, the probability is pretty high that there is a violation. Therefore, we need to reinstate them using a utility method, pushDown.
Back to our task management example. Let’s see what happens when calling top () on the ternary heap shown at the end of figure 2.9 (B).
First, at line #3 we remove the last element of the heap, at index [8], and save it to a temporary variable; at line #4 we check whether the remaining array is empty. If that had been the case, the last element in the array would also have been the top of the heap (its only element!) and we could have just returned it.
But this is clearly not the case in this example, so we move on to line #7, where we store the first element of the heap, <Unencrypted password on DB, 10>, to a temporary variable, which will be returned by the method. At this point, we can imagine the heap to be like what’s shown in figure 2.10 (A), three disconnected branches without a root. To sew them together, we add a new root, using the element we had saved at line #3, the one entry that used to be the last in the array, at index [8]. Figure 2.10 (B) shows the situation at this point.
This new root, however, is violating heap’s properties, so we need to call pushDown at line #8 to reinstate them by swapping it with its second children, whose priority is 9.5, and producing the heap shown in figure 2.10 (C); the pushDown method will handle this phase, stopping when the right position for element <Memory Leak, 9> is found.
To conclude this sub-section, it’s worth noting that the peek method returns the top element in the heap, but it just returns it without any side effects on the data structure. Its logic is therefore trivial, so we will skip its implementation.
5. Update
This is arguably the most interesting of heap’s public methods, even if it’s not always directly provided in implementations.[2]
When we change an element, its priority could stay unchanged, and in that case, we don’t need any further action. See listing 2.8. But it could also become lower or higher. If an element’s priority becomes higher, we need to check that it doesn’t violate the third invariant for its parents; if it becomes lower, it could violate the same invariant for its children.
In the former situation, we need to bubble up the modified element until we find a higher-priority ancestor or until we reach the root. In the latter, we instead push it down until all its children are lower priority, or we reach a leaf.
As we saw, the first case can always be implemented more efficiently[3] and luckily for us, most algorithms only require us to reduce elements’ priority.
Running time for update
From a performance point of view, the challenge of this method is in line #2: the search for the old element can take linear time in the worst case, because on a failed search (when the element is not actually in the heap), we will have to search the whole heap.
To improve this worst-case scenario, it is possible to use auxiliary data structures that will help us in performing searches more efficiently. For instance, we can store a map associating each element in the heap with its index. If implemented with a hash table, the lookup would only need an amortized o(1) time.
We will see this in further detail when describing the contains method. For now, let’s just remember that if the find operation takes at most logarithmic time, the whole method is also logarithmic.
6. Dealing with duplicates
So far, we’ve also assumed that our heap doesn’t hold duplicates. We will have to tackle further challenges if this assumption doesn’t hold true. In particular, we will need to figure out the order we use in case there are duplicates. To show why this is important, we will abandon our example for an easier configuration, illustrated in figure 2.11. For the sake of space we will only show priorities in nodes.
We could have two duplicates—call them X and Y—one being the child of the other. Let’s consider the case where X is a child of Y, and we call update to change their priority to a higher one. Inside update, after updating the two elements’ priorities, there would have to be two calls to bubbleUp, one for X, and one for Y. The catch is that if we run them in the wrong order, we will end with an inconsistent heap, which violates the heap’s properties.
Suppose we bubble up X, the children, first: then it will immediately find its parent (which is Y) and stop (because it has the same value). When we call bubbleUp(Y), we will discover that its parent now has lower priority, so we do need to move it toward the root. Unfortunately, we will never check X again, so it will never be moved up together with Y and heap’s property won’t be correctly reinstated.
Figure 2.11 provides a step-by-step description of how the update method could violate heap’s constraints if it’s not implemented in such a way to avoid duplicates:
- In step 1, we can see the initial max-heap.
- In step 2, all occurrences are changed from 4 to 8.
- In step 3, you see bubbling up the deepest node updated at index 3. It will stop immediately because its parent has the same priority (it just updated together with current node). The nodes involved in the call to bubbleUp are highlighted with a red outline.
- In step 4, you see bubbling up the other node that was updated at index 1. This time some swaps are actually performed as the node’s new priority, 8, is higher than its parent’s (just 7). The node that was bubbled up first, at step 3, will never be updated again, and so the heap’s properties will be violated.
How can we solve this issue? Following a left-to-right order for the calls to bubbleUp will guarantee that the heap properties are properly reinstated.
As an alternative, we could change the conditions in bubbleUp and pushDown, and only stop when we find a strictly higher-priority parent and strictly lower-priority children, respectively. Yet another alternative could be bubbling up (or pushing down) the nodes as we update them. Both these solutions, however, would be far from ideal for many reasons, not least performance-wise, because they would require a larger bound for the worst-case number of swaps (the proof is easy enough if you count the worst-case possible number of swaps in a path where all elements are the same— details are left to the reader).
7. Heapify
Priority queues can be created empty, but they are also often initialized with a set of elements. If that’s the case, and if we need to initialize the heap with n elements, we can still obviously create an empty heap and add those elements one by one.
To do so, we will need at most O(n) time to allocate the heap array, and then repeat n insertions. Every insertion is logarithmic, so we have an upper bound of O(n log n).
Is this the best we can do? Turns out that we can do better. Suppose that we initialize the heap with the whole sets of n elements, in any order.
As we have seen, each position of the array can be seen as the root of a sub-heap. So, leaves, for example, are trivial sub-heaps, containing only one element. Being singletons, they are valid heaps.
How many leaves are there in a heap? That depends on the branching factor. In a binary heap, half the nodes are leaves. In a 4-way heap, the last three-fourths of the array contain leaves.
Let’s stick to the case of a binary heap, for the sake of simplicity. We can see an example of a min-heap in figure 2.12, where we can follow step by step how heapify works.
If we start at the last internal node for the heap—let’s call it X—it will have at most two children, both leaves, and hence both valid heaps.
Figure 2.12 Heapification of a small array. The boxes with rounded corners surround valid sub-heaps; that is, portions of the tree for which we have verified that they abide by the heap properties. Step 1: Initially, only leaves are valid min-heap; here, smaller numbers mean higher priority. Step 2: The element from which we start our iteration is the first internal node in the heap, at index 2 in our array. In the bottom part of the leftmost figure, it is pointed at by an arrow. We repair the heap properties for the subheap rooted at this node by swapping its content with its child’s. Step 3: We move the arrow pointing to the current element one position to the left and repeat the operation for the sub-heap rooted at index 1. Step 4: Finally, the whole array is heapified, by pushing down the temporary root (with priority 5) until we find its right place.
We can’t say yet if X is the root of a valid heap, but we can try to push it down and possibly swap it with the smallest of its children. Once we have done that, we are sure that the sub-heap rooted at X is a valid heap. This happens because pushDown, by construction, reinstates the heap properties on a sub-heap where all children are valid heaps, and only the root might be misplaced.
If we now move one position left in the array, we can repeat the procedure, and get another valid sub-heap. Continuing on, at some point we visit all internal nodes that only have leaves as their children. And after that, we’ll start with the first internal node that’s the root of a sub-heap with height 2. Let’s name it Y. If we tackle elements in a right-to-left order in the array, we have the guarantee that Y’s children are sub-heaps that
- Have at most height 1 and
- Whose properties have already been fixed
Once again, we can use pushDown and be sure the sub-heap rooted at Y will be a valid heap afterward.
If we repeat these steps for all nodes until we reach the root of our heap, we have the guarantee that we will end up with a valid heap, as shown in listing 2.9.
We leave the computation for a d-ary heap as an exercise. It is similar to the previous one, replacing the branching factor.
8. Beyond API methods: Contains
One thing that heaps are definitely not good for is checking whether or not an element is stored in them. We have no other choice than going through all the elements until we find the one we were looking for, or we get to the end of the array. This means a linear time algorithm. Compare it with a hash table’s optimal average constant time, or even O(log(n)) for binary search trees (average) or balanced binary search trees (worst case).
However, we also would like to support priority increment/decrement. As we saw in section 2.6.5, it’s paramount for these operations to efficiently retrieve the element whose priority needs to be changed. Therefore, when implementing heaps, we might add an auxiliary field, a HashMap from elements to positions, that allows us to check whether an element is in the heap (or get its position) in constant time, on average. See a possible implementation of contains in listing 2.10.
Listing 2.10 The contains method
function contains(elem)
index ← elementToIndex[elem]
return index >= 0
The function uses an extra field elementToIndex we can add to our heap. This is possible under two assumptions:
- That elementToIndex[elem] by default returns -1 if elem is not stored in the heap.
- That we don’t allow duplicate keys in the heap; otherwise, we will need to store a list of indices for each key.
9. Performance recap
With the description of the contains method, we have concluded our overview of this data structure.
We have presented several operations on heaps, so it feels like the right time to order and recap their running time (table 2.4), and as importantly, show the amount of extra memory they need.
As with most things in computer science, time versus space is often a tradeoff. Nevertheless, sometimes there is a tendency to neglect the extra memory factor in informal analysis. With the volumes we’ve operated since the dawn of the era of big data, however, our data structures need to hold and process billions of elements, or even more. Therefore, a fast algorithm that consumes quadratic space could be the best choice for small volumes of data, but it becomes impractical for some real case scenarios where you need to scale out. And so a slower algorithm using constant or logarithmic space could be the choice of election as our dataset grows.
The takeaway is that it’s even more important to take the memory factor into account as early as possible when we design a system that needs to scale.
For heaps, consider that we naturally need constant extra space per element, and linear extra space in total, to host a map from elements to indices.
We have closely examined all operations. Yet, it’s worth spending a few more words on a couple of things.
For insert and top, the running time guarantee is amortized, not worst case. If a dynamic array is used to provide a flexible size, some calls will require linear time to resize the array. It can be proven that to fill a dynamic array with n elements, at most 2n swaps are needed. However, the worst-case logarithmic guarantee can be offered only if the heap size is set from the beginning. For this reason, and for allocation/garbage collection efficiency, in some languages (for instance, Java), it is advisable to initialize your heaps to their expected size, if you have a reasonable estimate that will remain true for most of the container’s life.
The performance for remove and updatePriority relies on the efficient implementation of contains, in order to provide a logarithmic guarantee. To have efficient search, however, we need to keep a second data structure besides the array for fast indirection. The choice is between a hash table or a bloom filter (see chapter 4).
In case either is used, the running time for contains is assumed to be constant, with a caveat: the hash for each element needs to be computable in constant time. Otherwise, we will need to take that cost into account in our analysis.
10. From pseudo-code to implementation
We have seen how a d-way heap works in a language-agnostic way. Pseudo-code provides a good way to outline and explain a data structure, without worrying about the implementation details so you can focus on its behavior.
At the same time, however, pseudo-code is of little practical use. To be able to move from theory to practice, we need to choose a programming language and implement our d-way heap. Independently of what platform we choose, language-specific concerns will arise and different problematics need to be taken into consideration.
We’ll provide implementations of the algorithms in this book, in an effort to give readers a way to experiment and get their hands dirty with these data structures.
The full code, including tests, can be found in our book’s repo on GitHub.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)