{"id":313,"date":"2023-08-14T01:25:28","date_gmt":"2023-08-14T01:25:28","guid":{"rendered":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/?post_type=chapter&#038;p=313"},"modified":"2026-10-14T11:59:26","modified_gmt":"2026-10-14T11:59:26","slug":"priority-queues","status":"publish","type":"chapter","link":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/chapter\/priority-queues\/","title":{"raw":"Priority Queues","rendered":"Priority Queues"},"content":{"raw":"<div class=\"textbox textbox--learning-objectives\"><header class=\"textbox__header\">\r\n<h2 class=\"textbox__title\">Learning Objectives<\/h2>\r\n<\/header>\r\n<div class=\"textbox__content\">\r\n<p class=\"import-Normal\">After reading this chapter you will\u2026<\/p>\r\n\r\n<ul>\r\n \t<li>understand the concept of a priority queue.<\/li>\r\n \t<li>understand the features of heaps, one of the most common priority queue implementations.<\/li>\r\n \t<li>be able to implement Heap Sort, a sorting algorithm that uses a priority queue.<\/li>\r\n \t<li>be able to explain the common operations on priority queues and their complexity.<\/li>\r\n \t<li>be able to implement a binomial heap that supports a fast union operation.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<\/div>\r\n<h2 class=\"import-Normal\">Introduction<\/h2>\r\n<p class=\"import-Normal\">We have already discussed the concept of a queue. This is a data structure that accepts items and removes them in the order they were inserted. This is often referred to as first-in-first-out, or FIFO. A priority queue serves like a regular queue allowing items to be inserted, but it allows for the item with the highest priority to exit the queue first. We could implement a priority queue as a simple array with a current capacity that just resorts all the items by priority every time an item is inserted. This would mean that the insert operation for our simple priority queue would be O(n log n). There may be more clever approaches to preserve the sorted order by moving things over. This might lead to an O(n) insert operation. Extract could work similarly by removing the first element and then copying all the elements over. Could we do better than O(n) though? Linear time might be a long time to wait for a large n. For example, suppose many players are waiting to start an online game. We could use a priority queue to add players to the next game based on how long they have been waiting. A game AI may want to prioritize and target players that are the most dangerous first. We will see in chapter 11 that priority queues are used as the foundation for some important graph algorithms. Since this type of data structure could be very useful, researchers and engineers have discovered a variety of data structures that greatly improve the time-cost complexity. We will explore two interesting implementations of priority queues in this chapter.<\/p>\r\n\r\n<h2 class=\"import-Normal\">Heaps<\/h2>\r\n<p class=\"import-Normal\">A heap is a data structure that guarantees that the minimum (or maximum) value is easily extracted. The most common heap is a binary heap, which is a sort of binary tree. In a binary heap, the \u201cleft\u201d or \u201cright\u201d position of a child node no longer carries any specific meaning. Rather, in a max-binary-heap, or just max-heap, the parent is guaranteed to be greater than both children. Min-binary-heaps naturally reverse that relationship, with the parent guaranteed to be less than the children. We call this quality the heap property. It will allow us to isolate our reasoning to only subheaps and thus aid our understanding of heap-related algorithms.<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For the remainder of this section, we assume max-binary-heaps to avoid confusion. We will also assume unique values in our binary heap. This simplifies the relationships between parents and their children. If a particular application of binary heaps necessitates duplicate keys, this is easily remedied by adjusting the appropriate comparisons. The figure below gives an example of a heap:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image176.png\" alt=\"Binary max-heap tree with 6 shaded nodes across three levels. Root node 12 has left child 7 and right child 4. Node 7 has two children, 3 and 5. Node 4 has a single left child, 2.\" width=\"803\" height=\"327\" \/><\/p>\r\n<p class=\"import-Normal\">Figure 9.1<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This distinction between parent and child nodes leads to two convenient properties of binary heaps:<\/p>\r\n\r\n<ul>\r\n \t<li class=\"import-Normal\">For a given heap, the maximum value (or key) is easily accessible at the root of the tree. As we will soon see, this implies not that it is easily extracted from the structure but simply that finding it is trivial.<\/li>\r\n \t<li class=\"import-Normal\">For any given node in a binary heap, all descendants contain values less than that node\u2019s value. In other words, any given subtree of a max-binary-heap is also a valid max-binary-heap.<\/li>\r\n<\/ul>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Let us emphasize and further address a common point of confusion. Although binary heaps are binary tree structures, their similarities with binary <em>search<\/em> trees (BST) end there. Recall from chapter 8 that an in-order traversal of a binary search tree will produce a sorted result. This is true because, for any given node in a BST, all left descendants are less than that node, and all right descendants are greater than it. In binary heaps, the left descendant is less than the parent, and the right descendant is less than it as well, but there is no other defined relationship between the two descendants.<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">To understand insertion and extraction, first note the shape of the binary tree above. A tree is a complete binary tree if each node has two children and all levels are filled except possibly the last, which is filled from left to right (chapter 8). Using some clever tricks, we can store a complete binary tree as an array. Because each level of the tree is filled and the last is filled left to right, we can simply list all elements in level 0, followed by all elements in level 1, and so on. Once these values are stored in an array, some simple arithmetic on the indexes allows traversal from a node to its parents or its children. We will be regularly adding and removing data from the heap itself. As we have seen in prior chapters, arrays are an insufficient data structure for accomplishing this. For the sake of simplicity, we will assume excess capacity at the end of the array. In practice, we would probably use some sort of abstract list that is able to grow or shrink and provides constant-time lookups. This might be something like an array that automatically reallocates when its capacity is reached. Implementations of these lists exist in most modern languages. For the present discussion, we can just treat the underlying storage as a typical array. The image below shows a heap represented as an array with integer values for the priorities:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.2%3A,times%202)%2B2.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image177-1.png\" alt=\"A binary heap encoded in an array. Each child is at a position 2*i + 1 or 2*i + 2 for any index of a parent. Click image for long description.\" width=\"901\" height=\"443\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.2<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For now, we will work only with integers that serve as the priorities themselves. To extend this into a more useful data structure, we would need only to change the contents of the array to an object or object reference. This would allow us to hold a more useful structure such as a student record or a game player\u2019s data. Then the only other change needed would be to do comparisons on array[index].priority instead of just array[index]. This modification is like the one we discussed regarding Linear Search in chapter 4. Recognize that we can generalize this representation easily to accommodate data records that are slightly more sophisticated than just integers.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Operations on Binary Heaps<\/h3>\r\n<p class=\"import-Normal\">Before we discuss the general operations on binary heaps, let\u2019s discuss some helper functions that will help us with our array representation. We will define functions that will allow us to find the parent, left child, and right child indexes given the index for any node in the tree structure. These would be helpful to define for any tree structure that we wanted to implement using an array. For this representation, the root will always be at the index 0. These are given in the figure above, but we will provide them as code here:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image178.png\" alt=\"1 function parent(index) 2 return floor((index-1)\/2).\" width=\"607\" height=\"43\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Here the floor function is the same as the mathematical function floor. It rounds down to the next integer.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image179-1.png\" alt=\"1 function leftChild(index) 2 return index*2 + 1.\" width=\"605\" height=\"43\" \/><\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image180.png\" alt=\"1 function rightChild(index) 2 return index*2 + 2.\" width=\"605\" height=\"43\" \/><\/p>\r\n\r\n<h4 class=\"import-Normal\">Heapify and Sift Up<\/h4>\r\n<p class=\"import-Normal\">Using the above functions to access positions in our tree, we can develop two important helper functions that will allow us to modify the tree and work to maintain our heap properties. These are the functions heapify and siftUp. When we are building our heap or modifying the priority of an item, these functions will be useful. The heapify function will exchange a parent with the larger of its children and then recursively heapify the subheap. The siftUp function will exchange a child with its parent to maintain the heap property by moving larger elements up the heap until it either is smaller than its parent or becomes the root node element. The siftUp function will be used when we want to increase the priority of an element. Let\u2019s look at the pseudocode for these functions in the context of an array-based max-heap implementation.<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The heapify function below lets a potentially small value work its way down the max-heap to find its correct place in the heap ordering of the tree. This code uses a size parameter that gives the current number of elements in the heap. This code also makes use of an exchange function like the one discussed in chapter 3 on sorting. This simply switches the elements of an array using indexes.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image181-1.png\" alt=\"1 function heapify(array, index, size) 2 set leftIndex to leftChild(index) 3 set rightIndex to rightChild(index) 4 5 # check if the left child is larger than parent 6 if leftIndex &lt; size and array[leftIndex] &gt; array[index] 7 set largest to leftIndex 8 else 9 set largest to index 10 11 # check if right is larger than current largest 12 if rightIndex &lt; size and array[rightIndex] &gt; array[largest] 13 set largest to rightIndex 14 15 if largest is not index 16 exchange(array, index, largest) 17 # recursively heapify the next subheap 18 heapify(array, largest, size).\" width=\"606\" height=\"264\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we will present the siftUp function. This function works in the reverse direction from heapify. It allows for a node with a potentially large value to make its way up the heap to the correct position to preserve the heap property. Since siftUp moves items toward index 0, the size is not needed. This does assume that the given index is valid.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image182-1.png\" alt=\"1 function siftUp(array, index) 2 while index &gt; 0 and array[parent(index)] &lt; array[index] 3 exchange(array, index, parent(index)) 4 set index to parent(index).\" width=\"617\" height=\"72\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">With these two helper functions, we can now implement the methods to insert elements and remove the max-element from our priority queue. Before we move on though, let\u2019s think about the complexity of these operations. Each of these methods moves items up or down the depths of a binary tree. If the tree could remain balanced, then a traversal from the top to bottom or bottom to top should only require O(log n) operations, assuming that the tree is balanced.<\/p>\r\n\r\n<h4 class=\"import-Normal\">Insertion<\/h4>\r\n<p class=\"import-Normal\">Consider inserting the number 8 into the prior binary heap example. Imagine if we simply added that 8 in the array after the 2 (in position 6).<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.3%3A,0%20through%206.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image183-1.png\" alt=\"The same heap as the previous figure with an 8 added to the end position. This position is incorrect according to heap ordering. Click image for long description.\" width=\"883\" height=\"453\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.3<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">What can we now claim about the state of our binary heap? Subheaps starting at indexes 1, 3, 4, and 5 are all still valid subheaps because the heap property is preserved. In other words, our erroneous insertion of 8 under 4 does not alter the descendants of these 4 nodes. As a result, we could hypothetically leave these subheaps unaltered in our corrected heap. This leaves nodes at indexes 0 and 2. These are the two nodes that have had their descendants altered. The heap property between node indexes 2 and 6 no longer holds, so let us start there. If we were to switch the 4 and 8, we would restore the heap property between those two indexes. We also know that moving 8 into index 2 will not affect the heap property between indexes 2 and 5. If 2 was less than 4 and 4 was found to be less than 8, switching the 4 and 8 does not impact the heap property between indexes 2 and 5. Once the 4 and 8 are in the correct positions, we know that the subheap starting at index 2 is correct. From here, we simply perform the same operations on subsequent parents until the next parent\u2019s value is greater than the value we are trying to insert. Given that we are inserting 8 and our root node\u2019s value is 12, we can stop iterating at this point. The pseudocode below is descriptive but much simpler than practical implementations, which must consider precise data structures for storing the heap. This provides the general pattern for inserting into a binary heap regardless of the underlying implementation. We place the new element at the end of the heap and then essentially siftUp that element to the place that will preserve the heap property.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image184-1.png\" alt=\"1 function insert(heap, value) 2 Add value at the end of the heap 3 set n to last element in heap 4 while n is not heap.root and n.value &gt; n.parent.value 5 exchange n and n.parent within heap 6 set n to n.parent.\" width=\"609\" height=\"99\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Runtime of insertion is independent of whether the heap is stored as object references or an array. In either case, we have to compare n.value to n.parent.value at most O(log n) times. Note that, unlike the caveat included in binary search trees (where traversing an unbalanced tree may be as slow as O(n)), binary heaps maintain their balance by building each new depth level before increasing its depth. This ensures that an imbalanced binary heap does not occur. This fact guarantees that our insert operation is O(log n).<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">A specific implementation for insert with our array-based heap is provided below:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image185-1.png\" alt=\"1 function insert(array, value) 2 # place the element at the end and update size 3 set array[size] to value 4 siftUp(array, size) 5 set size to size + 1.\" width=\"614\" height=\"86\" \/><\/p>\r\n\r\n<h4 class=\"import-Normal\">Extraction<\/h4>\r\n<p class=\"import-Normal\">Extraction is the process of removing the root node of a binary heap. It works much the same way as insertion but in reverse. The general strategy is as follows.<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">To extract an element from the heap\u2026<\/p>\r\n\r\n<ol>\r\n \t<li class=\"import-Normal\">Extract the root element, and prepare to return it.<\/li>\r\n \t<li class=\"import-Normal\">Replace the root with the last element in the heap.<\/li>\r\n \t<li class=\"import-Normal\">Call heapify on the new root to correct any violations of the heap property.<\/li>\r\n<\/ol>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As an example, consider our corrected heap from before. If we overwrite our 12 (at index 0) with the last value from the array (4 at index 6), the result will be as follows in figure 9.5. Just as we saw with insertion, many of our subheaps still have the heap property preserved. In fact, the only two places where the heap property no longer holds are from indexes 0 to 1 and 0 to 2. If the value at the root is less than the maximum value of its two children, then we swap the root value and that maximum. We will continue this process of pushing the root value down until the current node is greater than both children, thus conforming to the heap property. In this case, we swap the 4 with the 8. The root node conforms to the heap property because its children are 7 and 4. The node with value 4 (now at index 2) only has one child (2 at index 5). It conforms to the heap property, and our extraction is complete.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.4%3A,0%20through%206.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image186.png\" alt=\"The same heap as the previous figure with 8 now in its correct position according to heap ordering. Click image for long description.\" width=\"873\" height=\"442\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.4<\/p>\r\n\r\n<\/div>\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.5%3A%20Diagram%20of%20a%20binary%20tree%3A%20root%204%20(index%200)%20has%20children%207%20(index%201)%20and%208%20(index%202)%3B%20node%207%20has%20children%203%20(index%203)%20and%205%20(index%204)%3B%20node%208%20has%20a%20single%20left%20child%202%20(index%205).%20Below%20the%20tree%2C%20a%206%2Delement%20array%20shows%20the%20same%20values%20in%20level%20order%3A%204%2C%207%2C%208%2C%203%2C%205%2C%202%2C%20indexed%200%20through%205.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image187-1.png\" alt=\"The same heap as the previous figure after the max has been extracted. Click image for long description.\" width=\"868\" height=\"438\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.5<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As before, the pseudocode is much simpler than the actual implementation.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image188-1.png\" alt=\"1 function extract(heap) 2 set v to heap.root.value 3 set heap.root.value to heap.last.value 4 Delete heap.last.value 5 set n to heap.root 6 while n has children and n.value &lt; Max(n.left.value, n.right.value) 7 if Max(n.left.value, n.right.value) equals n.left.value 8 exchange n and n.left 9 set n to n.left 10 else 11 exchange n and n.right 12 set n to n.right 13 return v.\" width=\"627\" height=\"201\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The array-based implementation could use the heapify function to give the following code:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image189.png\" alt=\"1 function extract(array) 2 # save the max item to return 3 set maxItem to array[0] 4 5 # move the last item to the root, and update size 6 set array[0] to array[size - 1] 7 set size to size - 1 8 9 # now heapify the array from the root 10 heapify(array, 0, size) 11 12 return maxItem.\" width=\"609\" height=\"181\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">While accessing the max-element would only require O(1) time, updating the heap after it is removed requires a call to heapify. This function requires O(log n). While not constant time, O(log n) is a great improvement over our initial na\u00efve implementation ideas from the introduction. Our initial idea of sorting and then always copying moving elements up or down would have required O(n) operations to maintain our priority queue when inserting and removing elements. The max-heap greatly improves on these complexity estimates, giving O(log n) for both insert and extract.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Heap Sort<\/h3>\r\n<p class=\"import-Normal\">Heap Sort presents an interesting use of a priority queue. It can be used to sort the elements of an array. Once insertion and extraction have been defined, Heap Sort becomes a trivial step. We first build the heap, then repeatedly extract the maximum element and put it at the end of the array. Much like Selection Sort, Heap Sort will find the extreme value, place it into the correct position, then find the extreme of the remaining values. The trick is in how we perceive the heap. If we model it using an array, we can then sort the values in place by extracting the maximum. The extraction makes the heap smaller by one, but arrays are fixed size and still have the extra space allocated at the end. This portion at the end of the array becomes our sorted portion. As we perform more extractions and move those extracted values to the end of the array, our sorted portion gets bigger. See the figure below for an example. Unlike Selection Sort, where finding that extreme value requires an O(n) findMax or findMin, heaps allow us to extract the extreme value and revise our heap in O(log n) time. We perform this operation O(n) times, resulting in an O(n log n) sorting algorithm. The following figure gives an example execution of the sorting algorithm:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\" border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"7\" scope=\"colgroup\">heap<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\" border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"6\" scope=\"colgroup\">heap<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\" scope=\"colgroup\">\u00a0s<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%;height: 30px\" border=\"0\">\r\n<tbody>\r\n<tr style=\"height: 15px\">\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr style=\"height: 15px\">\r\n<td style=\"height: 15px;width: 14.2857%;text-align: center\" colspan=\"5\" scope=\"colgroup\">heap<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"2\">sorted<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\" border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"4\" scope=\"colgroup\">heap<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"3\" scope=\"colgroup\">sorted<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\" border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"3\" scope=\"colgroup\">heap<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"4\" scope=\"colgroup\">sorted<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%;height: 30px\" border=\"0\">\r\n<tbody>\r\n<tr style=\"height: 15px\">\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr style=\"height: 15px\">\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\" colspan=\"2\" scope=\"colgroup\">heap<\/td>\r\n<td style=\"width: 14.2857%;height: 15px;text-align: center\" colspan=\"5\" scope=\"colgroup\">sorted<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\" border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 14.2857%;text-align: center\" scope=\"colgroup\">h<\/td>\r\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"6\" scope=\"colgroup\">sorted<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p class=\"import-Normal\">Figure 9.6<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Before we give the implementation of Heap Sort, we should also mention how to build the heap in the first place. If we are given an array of random values, there is no guarantee that these will conform to our requirements of a heap. This is accomplished by calling the heapify function repeatedly to build valid heaps starting at the deeper levels of the balanced tree up to the root. Below is the code for buildHeap, which will take an array of elements to be sorted and put them into the correct heap ordering:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image191-1.png\" alt=\"1 function buildHeap(array) 2 set size to length(array) 3 # move the index up to the root by counting down 4 for index from size\/2 to 0 5 heapify(array, index, size).\" width=\"615\" height=\"86\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">It might be unintuitive, but buildHeap is O(n) in its time complexity. At first glance, we see heapify, an O(log n) operation, getting called inside a loop that runs from size\/2 down to 0. This might seem like O(n log n). What we need to remember though is that O(log n) is a worst-case scenario for heapify. It may be more efficient. As we build the heap up, we start at position size\/2. This is because half of the heap\u2019s elements will be leaves of the binary tree located at the deepest level. As we heapify the level just before the leaves, we only need to consider three elements: the parent and its two leaf children. As heapify runs, the amount of work is proportional to the height of the subtree it is operating on. Only on the very last call does heapify potentially visit all log n of the levels of the tree. We will omit the calculation details, but it has been proven that O(n) gives a tighter bound on the worst-case time complexity of buildHeap.<\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we are ready to implement Heap Sort. An implementation is provided below. Our O(n log n) complexity comes from calling heapify from the root every time we extract the next largest value. Another useful feature of this algorithm is that it is an <strong>in-place<\/strong> sorting algorithm. This means the extra space (auxiliary space) only consumes O(1) space in memory. So Heap Sort compares favorably to Quick Sort with a better worst-case complexity (O(n log n) vs. O(n<sup>2<\/sup>)), and it offers an improvement over Merge Sort in terms of its auxiliary space usage (O(1) auxiliary space vs. O(n)). We should note that Heap Sort may perform poorly in practice due to cache misses, since traversing a tree skips around the elements of the array.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image192.png\" alt=\"1 function heapSort(array) 2 # heap order the elements 3 buildHeap(array) 4 # repeatedly extract elements and place them in position 5 for index from (size - 1) to 1 6 set element to extract(array) 7 set array[index] to element.\" width=\"604\" height=\"113\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This section has provided an overview of heapSort and the concept of a heap more generally. Heaps are great data structures for implementing priority queues. They can be implemented using arrays or linked data structures. The array implementation also demonstrates an interesting example of embedding a tree structure into a linear array. The power and simplicity of heaps make them a popular data structure. One potential disadvantage of the heap is that merging two heaps might require O(n) operation. To combine these two heaps, we would need to create a new array, recopy the elements, and then call buildHeap, taking O(n) operations. In the next section, we will discuss a new data structure that supports an O(log n) <strong>union<\/strong> operation.<\/p>\r\n\r\n<h2 class=\"import-Normal\">Binomial Heaps<\/h2>\r\n<p class=\"import-Normal\">The <strong>binomial heap<\/strong> supports a fast union operation. When two heaps are given, union can combine them into a new heap containing all the combined elements from the two heaps. Binomial heaps are linked data structures, but they are a bit more complex than linked lists or binary trees. There is an interesting characteristic to their structure, which models the pattern of binary numbers, and combining them parallels binary addition. Binary numbers and powers of 2 seem to pop up everywhere in computer science. In this section, we will present the binomial heap and demonstrate how it can provide a fast union operation. Then we will see how many of the other operations on heaps can be implemented with clever use of the union function.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Linked Structures of Binomial Heaps<\/h3>\r\n<p class=\"import-Normal\">To build our heap, we need to discuss two main structures. The first part is the <strong>binomial tree<\/strong>. Each binomial tree is composed of connected <strong>binomial nodes<\/strong>. The structure of a binomial tree can be described recursively. Each binomial tree has a value k that represents its degree. The degree 0 tree, B<sub>0<\/sub>, has one element and no children. A degree k tree, B<sub>k<\/sub>, has k direct children but 2<sup>k<\/sup> nodes in total. When the B<sub>k<\/sub> tree is constructed, the roots of two B<sub>k\u22121<\/sub> trees are examined. The largest root of the two trees is assigned as the root of the new tree, assuming a <strong>max-binomial-heap<\/strong>. The heap is then represented as a <strong>list of binomial trees<\/strong>. A collection of trees is known as a <strong>forest<\/strong>. The main idea of the binomial is that each heap is a list of trees, and to combine the two heaps, one just needs to combine all the trees of equal degree. To facilitate this, the trees are always ordered by increasing tree degrees. A few illustrations will help you understand this process a little better.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.7%3A,2%C3%972%5E2).\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image193-1.png\" alt=\"Examples of binomial trees with degrees given. Each degree starting at zero give the number of children of the root node of the tree. Each binomial tree contains 2 to the degree power nodes. Click image for long dsecription.\" width=\"922\" height=\"378\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.7<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Using these trees, a heap would then be a list of these trees. To preserve the max-heap property, any node\u2019s priority must be larger than its child. Below is an example binomial heap. Let\u2019s call this heap<sub>A<\/sub>:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.8%3A,no%20children%20(B0)\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image194.png\" alt=\"Example binomial heap with degree 0, degree 1, and degree 3 trees. Click image for long description.\" width=\"985\" height=\"332\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.8<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Notice that the maximum element is in B<sub>1<\/sub> tree of this heap. This illustrates that the actual max-heap element is one of the root nodes of trees in the list. Now we can make the connection to binary numbers. This heap will either have a tree of any given degree or not. This could be indicated by a 0 or 1. So the above heap has a degree 0 tree, a degree 1 tree, and a degree 3 tree. In binary with the bits correctly ordered, this would be 1011<sub>2<\/sub> or the number 11<sub>10<\/sub> in base 10. Suppose there is another heap, heap<sub>B<\/sub>, that we wish to merge with. This is given below:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.9%3A%20Diagram%20of%20a%20binomial%20heap%20labeled%20heapB%2C%20showing%20a%20root%20list%20of%20two%20binomial%20trees%20connected%20by%20a%20horizontal%20arrow%3A%2025%20(B1%2C%20one%20child%3A%2013)%20and%2017%20(B2%2C%20two%20children%3A%2014%20and%206%2C%20where%2014%20has%20its%20own%20child%204)\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image195-1.png\" alt=\"A second binomial heap with degree 1 and degree 2 trees. Click image for long description.\" width=\"967\" height=\"237\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.9<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This heap has trees for degrees 1 and 2. In binary, we could represent this pattern as 110<sub>2<\/sub> or the number 6<sub>10<\/sub> in base 10. We will soon look at how these heaps could be merged, but first let\u2019s consider the process of binary addition for these two binary numbers: 11 and 6. The figure below gives an example of the addition:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.10%3A%20Diagram%20showing%20binary%20place%20values%20and%20a%20binary%20addition%20example.%20Top%20table%20lists%20powers%20of%20two%20with%20their%20values%3A%202%E2%81%B4%3D16%2C%202%C2%B3%3D8%2C%202%C2%B2%3D4%2C%202%C2%B9%3D2%2C%202%E2%81%B0%3D1.%20Below%2C%20a%20binary%20addition%20is%20shown%3A%201011%20plus%200110%2C%20with%20carried%201s%20written%20above%20the%202%C2%B3%20and%202%C2%B2%20columns%2C%20giving%20a%20sum%20of%2010001.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image196.png\" alt=\"Diagram of binary addition for the number 11 and 6 represented in binary. The diagram show the power of 2 places and the carry from addition of lower places. Click image for long description.\" width=\"964\" height=\"255\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.10<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This diagram of binary addition also demonstrates how our trees need to be combined to create the correct structure for our unified trees. The following images will show these steps in action. First, we will merge the two lists into another list (but not a heap yet). This merge is similar to the merge operation in Merge Sort:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.11%3A,subtrees%20as%20before).\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image197-1.png\" alt=\"An intermediate stage of a binomial heap union. This represents the state of the heap list after a merge, but before resolving all the binomial trees. Click image for long description.\" width=\"955\" height=\"680\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.11<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Next, the algorithm will examine two trees at a time to determine if the trees are the same degree. Any trees that have an equal degree will be merged. Because the nodes are ordered by degree, we only need to consider two nodes at a time and potentially keep track of a carry node.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.12%3A,down%20to%2012.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image198-1.png\" alt=\"The algorithm considers pairs of trees and tries to determine if the need to be combined. Click image for long description.\" width=\"950\" height=\"351\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.12<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">These nodes are not equal in degree. We can move on.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.13%3A,down%20to%2012.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image199-1.png\" alt=\"The algorithm combines any two trees of equal degree. Here two trees of degree 2 would be merged. Click image for long description.\" width=\"979\" height=\"363\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.13<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we are considering two nodes of equal degree. These two B<sub>1<\/sub> trees need to become a B<sub>2<\/sub> tree.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.14%3A,of%20preceding%20it.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image200.png\" alt=\"The algorithm continues and combines two trees of degree 2 to form one degree 3 tree. Click image for long description.\" width=\"943\" height=\"351\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.14<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">After combining the B<sub>1<\/sub> trees, we now have two B<sub>2<\/sub> trees that need to be combined. This will be done such that the maximum item of the roots becomes the new root.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.15%3A,root%20node%2018.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image201-1.png\" alt=\"The algorithm combines two degree 3 trees. Click image for long description.\" width=\"931\" height=\"364\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.15<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Again, the \u201ccarry\u201d from addition means that we now have two B<sub>3<\/sub> trees to merge. This step creates a B<sub>4<\/sub> tree with 2<sup>4<\/sup> = 16 nodes. The final merged heap is below, with one B<sub>0<\/sub> node and one B<sub>4<\/sub> node:<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.16%3A,Has%20no%20children.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image202.png\" alt=\"Finally, the unioned heaps have 1 degree 0 tree and one degree 4 tree. Click image for long description.\" width=\"885\" height=\"350\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.16<\/p>\r\n\r\n<\/div>\r\n<h3 class=\"import-Normal\">Implementing Binomial Trees<\/h3>\r\n<p class=\"import-Normal\">To implement Binomial trees, we will need to create a node class with appropriate links. Again, we will use references, also known as pointers, for our links. A node\u2014and by extension, a tree\u2014can be represented with the BinomialTree class below. In this class, Data would be any entity that needed storing in the priority queue:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image203-1.png\" alt=\"1 Class BinomialTree 2 Data data 3 Integer priority 4 Integer degree 5 # links to other nodes 6 BinomialTree parent 7 BinomialTree sibling 8 BinomialTree child.\" width=\"623\" height=\"130\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For the BinomialHeap itself, we only need a reference to the first tree in the forest. This simple pseudocode is presented below:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image204.png\" alt=\"1 class BinomialHeap 2 BinomialTree head.\" width=\"624\" height=\"44\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As we progress toward a complete implementation, we will build up the operation that we need, working toward the union operation. Once union is implemented, adding or removing items from the heap can be implemented through the clever usage of union. For now, let\u2019s implement the combine and merge functions.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Combining Two Binomial Trees<\/h3>\r\n<p class=\"import-Normal\">The combine function is given below. This simple function combines two B<sub>k\u22121<\/sub> trees to create a new B<sub>k<\/sub> tree. This function will make the first tree a child of the second tree. We will assume that tree1.priority is always less than or equal to tree2.priority.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image205-1.png\" alt=\"1 function combine(tree1, tree2) 2 set tree1.parent to tree2 3 set tree1.sibling to tree2.child 4 set tree2.child to tree1 5 set tree2.degree to tree2.degree + 1.\" width=\"616\" height=\"86\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The figure below shows how two B<sub>2<\/sub> trees would be combined to form a B<sub>3<\/sub> tree. This figure also identifies the parent, sibling, and child links for each node. Links that do not connect to any other node have the value null. This figure can help you understand the combine function. We need to maintain these links in a specific way to make the other operations function correctly. Notice that the children of the root are all linked together by sibling links, like a linked list\u2019s next reference.<\/p>\r\n\r\n<div class=\"textbox standard\">\r\n<p class=\"import-Normal\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.17%3A%20The%20diagram%20is%20split%20into%20two%20halves,vertical%20upward%20arrow%20pointing%20back%20to%20the%20root%2C%20node%2025.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image206-1.png\" alt=\"Two degree 2 trees ready to be merged. The resulting degree 3 tree has 3 children. These children are a degree 0 tree, a degree 1 tree, and a degree 2 tree. Click image for long description.\" width=\"914\" height=\"363\" \/><\/a><\/p>\r\n<p class=\"import-Normal\">Figure 9.17<\/p>\r\n\r\n<\/div>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Another interesting feature of binomial trees is that each tree of degree k contains subtrees of all the degrees below it. These are the children linked from the first child of the new tree. For example, the B<sub>3<\/sub> tree contains a B<sub>0<\/sub>, B<sub>1<\/sub>, and B<sub>2<\/sub> subtree in descending order. You can observe these in the figure above. This fact will come in handy when we implement the extract function for binomial heaps.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Merging Heaps<\/h3>\r\n<p class=\"import-Normal\">Now that we can combine two trees to form a higher-degree tree, we should implement the mergeHeaps function. This will take both heaps and their forests of binomial trees and merge them. You can think of these \u201cforests\u201d as linked lists of binomial trees. Once these forests are merged, trees of equal degree will be adjacent in the list. This sets the stage for our \u201cbinary addition\u201d algorithm that will calculate the union of both heaps. The code for mergeHeaps is below:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image207-1.png\" alt=\"1 function mergeHeaps(heap1, heap2) 2 set tree1 to heap1.head 3 set tree2 to heap2.head 4 set newHeap to an instance of BinomialHeap 5 # if either heap is null, return the other 6 if tree1 equals null 7 return tree2 8 if tree2 equals null 9 return tree1 10 11 # set the heap's head to the lowest degree tree 12 if tree1.degree &lt;= tree2.degree 13 set newHeap.head to tree1 14 else 15 set newHeap.head to tree2 16 set current to newHeap.head 17 while (tree1 is not null) and (tree2 is not null) 18 if tree1.degree &lt;= tree2.degree 19 # update sibling links 20 set current.sibling to tree1 21 set current to current.sibling 22 # advance to tree1's next node 23 set tree1 to tree1.sibling 24 else 25 # if this is not the first node, update sibling links 26 set current.sibling to tree2 27 set current to current.sibling 28 # advance to tree2's next node 29 set tree2 to tree2.sibling 30 31 # tree1 or tree2 is null 32 # end of one list was reached 33 if tree1 equals null 34 set current.sibling to tree2 35 else 36 set current.sibling to tree1 37 38 return newHeap.head.\" width=\"624\" height=\"554\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This may look a little difficult to follow, but the concept is simple. Starting with links to the lists of binomial trees, we first check to see if any of these are null. If so, we just return the other one. Afterward, we check which of the nonnull trees has the lowest degree and set our newHeap\u2019s head to this tree. The while-loop then appends the tree with the next smallest degree to the growing list. The loop continues until one of the two lists of trees reaches its end. After that, the remaining trees are linked to the list by the current reference, and the head of our merged list is returned. Notice that the sibling references serve the same role as the next pointers of a linked list.<\/p>\r\n\r\n<h3 class=\"import-Normal\">The Binomial Heap Union Operation<\/h3>\r\n<p class=\"import-Normal\">Now we will tackle the union function. This function performs the final step of combining two binomial heaps by traversing the merged list and combining any pairs of trees that have equal degrees. The algorithm is given below:<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image208-1.png\" alt=\"1 function union(heap1, heap2) 2 set newHeap to an instance of BinomialHeap 3 set newHeap.head to mergeHeaps(heap1, heap2) 4 if newHeap.head equals null 5 return newHeap 6 7 # create references to traverse the merged list 8 set previousTree to null 9 set currentTree to newHeap.head 10 set nextTree to newHeap.sibling 11 12 while nextTree is not null 13 # advance the traversal cases 14 if (currentTree.degree is not nextTree.degree) or 15 ((nextTree.sibling is not null) and 16 (currentTree.degree equals nextTree.sibling.degree)) 17 set previousTree to currentTree 18 set currentTree to nextTree 19 else 20 # combine the trees with equal degree by priority 21 if currentTree.priority &gt;= nextTree.priority 22 set currentTree.sibling to nextTree.sibling 23 # currentTree has higher priority 24 combine(nextTree, currentTree) 25 else 26 # first node? make sure to update the heap's head 27 if previousTree equals null 28 set newHeap.head to nextTree 29 else 30 set previousTree.sibling to nextTree 31 # nextTree has higher priority 32 combine(currentTree, nextTree) 33 set nextTree to currentTree.sibling 34 return newHeap.\" width=\"627\" height=\"498\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The union function begins by setting up a new, empty heap and then merging the two input heaps. Once the merged list of trees is generated, the algorithm traverses the list using three references (previousTree, currentTree, and nextTree). The code will advance the traversal forward if currentTree and nextTree have different degree values. Another case that moves the traversal forward is when nextTree.sibling has the same degree as currentTree and nextTree. This is because nextTree and nextTree.sibling will need to combine to occupy the k + 1 degree level. When a call to combine is needed, the algorithm checks which tree has the highest priority, and that tree\u2019s root becomes the root of the k + 1 tree.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Time Complexity of Union<\/h3>\r\n<p class=\"import-Normal\">The union operation is completed, but now we should analyze its complexity. One of the main reasons for choosing a binomial heap was its fast union operation. How fast is it though? We will be interested in the time complexity of union. The algorithm traverses both heaps for the merge and the sequence combinations. This means that the complexity is proportional to the number of trees. We need to determine how many binomial trees are needed to represent all n elements of the priority queue. Recall that there are many parallels between binomial heaps and binary numbers. If we have 3 items in our heap, we need a tree of degree 0 with 1 item and a tree of degree 1, with 2 items. To store 5 items, we would need a degree 0 tree with 1 item, and a degree 2 tree with 4 items. Here we see that the binary representation of n indicates which trees of any given degree are needed to store those elements. A number can be represented in binary using a maximum number of bits proportional to the log of that number. So there are log n trees in a binomial heap with n elements. This means that the time complexity of union is bounded by O(log n). By similar reasoning, the time cost for finding the element with the highest priority is O(log n), the number of binomial trees in the heap.<\/p>\r\n\r\n<h3 class=\"import-Normal\">Inserting into a Binomial Heap<\/h3>\r\n<p class=\"import-Normal\">With union completed, we can see the benefit of this operation. Below is an implementation of insert using union. The union operation takes O(log n) time, and all other operations can be performed in O(1) time. This makes the time complexity for insert O(log n).<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image209-1.png\" alt=\"1 function insert(heap, data, priority) 2 # create a new heap 3 set newHeap to an instance of BinomialHeap 4 5 # create a tree node 6 set tree to an instance of BinomialTree 7 set tree.data to data 8 set tree.priority to priority 9 set tree.degree to 0 10 set tree.parent to null 11 set tree.sibling to null 12 set tree.child to null 13 14 # add degree 0 tree to heap 15 set newHeap.head to tree 16 17 # union the heap and the new heap to insert 18 return union(heap, newHeap).\" width=\"619\" height=\"270\" \/><\/p>\r\n\r\n<h3 class=\"import-Normal\">Extracting the Max-Priority Element<\/h3>\r\n<p class=\"import-Normal\">The priority queue would not be complete without a function to extract the maximum element from the heap. The extract function takes a bit more work, but ultimately extract executes in O(log n) time. The maximum priority element must be the root of one of the heap\u2019s trees. This function will find the maximum priority element and remove its entire tree from the heap\u2019s tree list. Next, the children of the max-element are inserted into another heap. With the two valid heaps, we can now call union to create the binomial heap that results from removing the highest priority element. This element can be returned, and the binomial heap will have been updated to reflect its new state. We note that in this implementation, there is a side effect of extract. This function returns the maximum priority element and removes it from the input heap as a side effect that modifies the input. Another approach would be to implement an accessMax function to find the maximum priority element and return it without updating the heap. This means that extracting the element would require a call to accessMax to save the element, and then extract would be called. We could also consider extracting part of the BinomialHeap class and avoid passing any heap as input.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image210.png\" alt=\"1 function extract(heap) 2 # first, find tree with max item 3 set previousTree to null 4 set currentTree to heap.head 5 if currentTree equals null 6 return null 7 8 set maxTree to currentTree 9 set maxPreviousTree to previousTree 10 11 while currentTree is not null 12 if currentTree.priority &gt; maxTree.priority 13 set maxTree to currentTree 14 set maxPreviousTree to previousTree 15 set previousTree to currentTree 16 set currentTree to currentTree.sibling 17 18 # connect previous tree to next tree in the heap 19 if maxPreviousTree equals null 20 # max is the first tree 21 set heap.head to maxTree.sibling 22 else 23 set maxPreviousTree.sibling to maxTree.sibling 24 25 # make a new heap for maxTree's children 26 set newHeap to an instance of BinomialHeap 27 set currentTree to maxTree.child 28 29 # reverse and add children to the new heap 30 while currentTree is not null 31 # save the next node 32 set nextTree to currentTree.sibling 33 # add trees to the front of the list, reverse the order 34 set currentTree.sibling to newHeap.head 35 set currentTree.parent to null 36 set newHeap.head to currentTree 37 set currentTree to nextTree 38 39 # now union modified heap and the heap of the max element's children 40 set heap to union(heap, newHeap) 41 return maxTree.\" width=\"621\" height=\"593\" \/><\/p>\r\n\r\n<h3 class=\"import-Normal\">Increase-Priority and Delete Operations<\/h3>\r\n<p class=\"import-Normal\">We will continue our theme of building new operations by combining old ones. Here we will present the delete operation. This operation will make use of extract and increasePriority, which we will develop next. Creating the increasePriority function will rely on the parent points that we have been maintaining. When the priority of an element is increased, it may need to work its way up the tree structure toward the root. The following code gives an implementation of increasePriority. We assume for simplicity that we already have a link to the element whose priority we want to increase. The element with the highest priority moves up the tree just like in the binary heap\u2019s siftUp operation.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image211-1.png\" alt=\"1 function increasePriority(heap, tree, newPriority) 2 if tree.priority &gt; newPriority 3 # do nothing if the new priority is less than the old. 4 return 5 6 set tree.priority to newPriority 7 set currentTree to tree 8 set parentTree to tree.parent 9 while (parentTree is not null) and (currentTree.priority &gt; parentTree.priority) 10 # exchange the data and priority of the current and parent trees 11 set temporaryData to parentTree.data 12 set parentTree.data to currentTree.data 13 set currentTree.data to temporaryData 14 15 set temporaryPriority to parentTree.priority 16 set parentTree.priority to currentTree.priority 17 set currentTree.priority to temporaryPriority 18 19 # move references up the tree toward the root 20 set currentTree to parentTree 21 set parentTree to parentTree.parent.\" width=\"619\" height=\"295\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we can implement delete very easily using the MAX special value. We increase the element\u2019s priority to the maximum possible value and then call extract. An implementation of delete is provided below. Again, we assume that a link to the element we wish to delete is provided.<\/p>\r\n<p class=\"import-Normal\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image212-1.png\" alt=\"1 function delete(heap, tree) 2 increasePriority(heap, tree, MAX) 3 extract(heap).\" width=\"617\" height=\"58\" \/><\/p>\r\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The time complexity of delete is derived from the complexity of increasePriority and extract. Each of these requires O(log n) time.<\/p>\r\n\r\n<h3 class=\"import-Normal\">A Note on the Name<\/h3>\r\n<p class=\"import-Normal\">Before we close this chapter on priority queues, we should discuss why these are called binomial heaps. The name \u201cbinomial heap\u201d comes from a property that for a binomial tree of degree k, the number of nodes at a given depth d is k <em>choose<\/em> d. This is written as [latex]{\\large (k \\;d) = \\frac{k!}{d!(k-d)!}}[\/latex]<\/p>\r\n\r\n<h2 class=\"import-Normal\">Summary<\/h2>\r\n<p class=\"import-Normal\">In this chapter, we explored one of the most important abstract data types: the priority queue. This data structure provides a collection that supports efficient insert and remove operations with the added benefit of removing elements in order of priority. We looked at two important implementations. One implementation used an array and created a binary heap. We also saw that this structure can be used to implement an in-place O(n log n) sorting algorithm by simply extracting elements from the queue and placing them in the sorted zone of the array. Next, we explored the binomial heap\u2019s implementation. This data structure provides an O(log n) union operation. Though the implementation of binomial heaps seems complex, there is an interesting and beautiful simplicity to its structure. Our union algorithm also draws parallels to the addition of binary numbers, making it an interesting data structure to study. Any student of computer science should understand the concept of priority queues. They form the foundation of some interesting algorithms. For example, chapter 11 on graphs will present an algorithm for a minimum spanning tree that relies on an efficient priority queue. The minimum spanning tree is the backbone of countless interesting and useful algorithms. Hopefully, by now, you are beginning to see how data structures and algorithms build on each other through composition.<\/p>\r\n&nbsp;\r\n<div class=\"textbox textbox--exercises\"><header class=\"textbox__header\">\r\n<h2 class=\"textbox__title\">Exercises<\/h2>\r\n<\/header>\r\n<div class=\"textbox__content\">\r\n<ol class=\"legal\">\r\n \t<li class=\"import-Normal\">Implement Heap Sort on arrays in the language of your choice. Revisit your work from chapter 3 on sorting. Using your testing framework, compare Heap Sort, Merge Sort, and Quick Sort. Which seems to perform better on average in terms of speed? Why would this be the case on your machine?<\/li>\r\n \t<li class=\"import-Normal\">What advantages would Heap Sort have over Quick Sort? What advantages would Heap Sort have over Merge Sort?<\/li>\r\n \t<li class=\"import-Normal\">Extend your heap implementation to use references to data records with a priority variable rather than just an integer as the priority.<\/li>\r\n \t<li class=\"import-Normal\">Implement both binomial heaps using linked structures and binary heaps using an array implementation. Using a random number generator, create two equal-sized heaps, and try to merge them. Try the merge with binomial heaps, and get some statistics for the merge speed. Compare with the merge speed of binary heaps with integers. Repeat this process several times to explore how larger n affects the speed of the rival heap merge algorithms. The results may not be what you expect. How might caches play a role in the speed of these algorithms?<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox textbox--key-takeaways\"><header class=\"textbox__header\">\r\n<h2 class=\"textbox__title\">References<\/h2>\r\n<\/header>\r\n<div class=\"textbox__content\">\r\n<p class=\"import-Normal hanging-indent\">Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. <em>Introduction to Algorithms<\/em>, 2nd ed. Cambridge, MA: The MIT Press, 2001.<\/p>\r\n<p class=\"import-Normal hanging-indent\">Vuillemin, Jean. \u201cA Data Structure for Manipulating Priority Queues.\u201d <em>Communications of the ACM<\/em> 21, no. 4 (1978): 309\u2013315.<\/p>\r\n\r\n<\/div>\r\n<\/div>","rendered":"<div class=\"textbox textbox--learning-objectives\">\n<header class=\"textbox__header\">\n<h2 class=\"textbox__title\">Learning Objectives<\/h2>\n<\/header>\n<div class=\"textbox__content\">\n<p class=\"import-Normal\">After reading this chapter you will\u2026<\/p>\n<ul>\n<li>understand the concept of a priority queue.<\/li>\n<li>understand the features of heaps, one of the most common priority queue implementations.<\/li>\n<li>be able to implement Heap Sort, a sorting algorithm that uses a priority queue.<\/li>\n<li>be able to explain the common operations on priority queues and their complexity.<\/li>\n<li>be able to implement a binomial heap that supports a fast union operation.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<h2 class=\"import-Normal\">Introduction<\/h2>\n<p class=\"import-Normal\">We have already discussed the concept of a queue. This is a data structure that accepts items and removes them in the order they were inserted. This is often referred to as first-in-first-out, or FIFO. A priority queue serves like a regular queue allowing items to be inserted, but it allows for the item with the highest priority to exit the queue first. We could implement a priority queue as a simple array with a current capacity that just resorts all the items by priority every time an item is inserted. This would mean that the insert operation for our simple priority queue would be O(n log n). There may be more clever approaches to preserve the sorted order by moving things over. This might lead to an O(n) insert operation. Extract could work similarly by removing the first element and then copying all the elements over. Could we do better than O(n) though? Linear time might be a long time to wait for a large n. For example, suppose many players are waiting to start an online game. We could use a priority queue to add players to the next game based on how long they have been waiting. A game AI may want to prioritize and target players that are the most dangerous first. We will see in chapter 11 that priority queues are used as the foundation for some important graph algorithms. Since this type of data structure could be very useful, researchers and engineers have discovered a variety of data structures that greatly improve the time-cost complexity. We will explore two interesting implementations of priority queues in this chapter.<\/p>\n<h2 class=\"import-Normal\">Heaps<\/h2>\n<p class=\"import-Normal\">A heap is a data structure that guarantees that the minimum (or maximum) value is easily extracted. The most common heap is a binary heap, which is a sort of binary tree. In a binary heap, the \u201cleft\u201d or \u201cright\u201d position of a child node no longer carries any specific meaning. Rather, in a max-binary-heap, or just max-heap, the parent is guaranteed to be greater than both children. Min-binary-heaps naturally reverse that relationship, with the parent guaranteed to be less than the children. We call this quality the heap property. It will allow us to isolate our reasoning to only subheaps and thus aid our understanding of heap-related algorithms.<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For the remainder of this section, we assume max-binary-heaps to avoid confusion. We will also assume unique values in our binary heap. This simplifies the relationships between parents and their children. If a particular application of binary heaps necessitates duplicate keys, this is easily remedied by adjusting the appropriate comparisons. The figure below gives an example of a heap:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image176.png\" alt=\"Binary max-heap tree with 6 shaded nodes across three levels. Root node 12 has left child 7 and right child 4. Node 7 has two children, 3 and 5. Node 4 has a single left child, 2.\" width=\"803\" height=\"327\" \/><\/div>\n<p class=\"import-Normal\">Figure 9.1<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This distinction between parent and child nodes leads to two convenient properties of binary heaps:<\/p>\n<ul>\n<li class=\"import-Normal\">For a given heap, the maximum value (or key) is easily accessible at the root of the tree. As we will soon see, this implies not that it is easily extracted from the structure but simply that finding it is trivial.<\/li>\n<li class=\"import-Normal\">For any given node in a binary heap, all descendants contain values less than that node\u2019s value. In other words, any given subtree of a max-binary-heap is also a valid max-binary-heap.<\/li>\n<\/ul>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Let us emphasize and further address a common point of confusion. Although binary heaps are binary tree structures, their similarities with binary <em>search<\/em> trees (BST) end there. Recall from chapter 8 that an in-order traversal of a binary search tree will produce a sorted result. This is true because, for any given node in a BST, all left descendants are less than that node, and all right descendants are greater than it. In binary heaps, the left descendant is less than the parent, and the right descendant is less than it as well, but there is no other defined relationship between the two descendants.<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">To understand insertion and extraction, first note the shape of the binary tree above. A tree is a complete binary tree if each node has two children and all levels are filled except possibly the last, which is filled from left to right (chapter 8). Using some clever tricks, we can store a complete binary tree as an array. Because each level of the tree is filled and the last is filled left to right, we can simply list all elements in level 0, followed by all elements in level 1, and so on. Once these values are stored in an array, some simple arithmetic on the indexes allows traversal from a node to its parents or its children. We will be regularly adding and removing data from the heap itself. As we have seen in prior chapters, arrays are an insufficient data structure for accomplishing this. For the sake of simplicity, we will assume excess capacity at the end of the array. In practice, we would probably use some sort of abstract list that is able to grow or shrink and provides constant-time lookups. This might be something like an array that automatically reallocates when its capacity is reached. Implementations of these lists exist in most modern languages. For the present discussion, we can just treat the underlying storage as a typical array. The image below shows a heap represented as an array with integer values for the priorities:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.2%3A,times%202)%2B2.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image177-1.png\" alt=\"A binary heap encoded in an array. Each child is at a position 2*i + 1 or 2*i + 2 for any index of a parent. Click image for long description.\" width=\"901\" height=\"443\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.2<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For now, we will work only with integers that serve as the priorities themselves. To extend this into a more useful data structure, we would need only to change the contents of the array to an object or object reference. This would allow us to hold a more useful structure such as a student record or a game player\u2019s data. Then the only other change needed would be to do comparisons on array[index].priority instead of just array[index]. This modification is like the one we discussed regarding Linear Search in chapter 4. Recognize that we can generalize this representation easily to accommodate data records that are slightly more sophisticated than just integers.<\/p>\n<h3 class=\"import-Normal\">Operations on Binary Heaps<\/h3>\n<p class=\"import-Normal\">Before we discuss the general operations on binary heaps, let\u2019s discuss some helper functions that will help us with our array representation. We will define functions that will allow us to find the parent, left child, and right child indexes given the index for any node in the tree structure. These would be helpful to define for any tree structure that we wanted to implement using an array. For this representation, the root will always be at the index 0. These are given in the figure above, but we will provide them as code here:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image178.png\" alt=\"1 function parent(index) 2 return floor((index-1)\/2).\" width=\"607\" height=\"43\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Here the floor function is the same as the mathematical function floor. It rounds down to the next integer.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image179-1.png\" alt=\"1 function leftChild(index) 2 return index*2 + 1.\" width=\"605\" height=\"43\" \/><\/div>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image180.png\" alt=\"1 function rightChild(index) 2 return index*2 + 2.\" width=\"605\" height=\"43\" \/><\/div>\n<h4 class=\"import-Normal\">Heapify and Sift Up<\/h4>\n<p class=\"import-Normal\">Using the above functions to access positions in our tree, we can develop two important helper functions that will allow us to modify the tree and work to maintain our heap properties. These are the functions heapify and siftUp. When we are building our heap or modifying the priority of an item, these functions will be useful. The heapify function will exchange a parent with the larger of its children and then recursively heapify the subheap. The siftUp function will exchange a child with its parent to maintain the heap property by moving larger elements up the heap until it either is smaller than its parent or becomes the root node element. The siftUp function will be used when we want to increase the priority of an element. Let\u2019s look at the pseudocode for these functions in the context of an array-based max-heap implementation.<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The heapify function below lets a potentially small value work its way down the max-heap to find its correct place in the heap ordering of the tree. This code uses a size parameter that gives the current number of elements in the heap. This code also makes use of an exchange function like the one discussed in chapter 3 on sorting. This simply switches the elements of an array using indexes.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image181-1.png\" alt=\"1 function heapify(array, index, size) 2 set leftIndex to leftChild(index) 3 set rightIndex to rightChild(index) 4 5 # check if the left child is larger than parent 6 if leftIndex &lt; size and array[leftIndex] &gt; array[index] 7 set largest to leftIndex 8 else 9 set largest to index 10 11 # check if right is larger than current largest 12 if rightIndex &lt; size and array[rightIndex] &gt; array[largest] 13 set largest to rightIndex 14 15 if largest is not index 16 exchange(array, index, largest) 17 # recursively heapify the next subheap 18 heapify(array, largest, size).\" width=\"606\" height=\"264\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we will present the siftUp function. This function works in the reverse direction from heapify. It allows for a node with a potentially large value to make its way up the heap to the correct position to preserve the heap property. Since siftUp moves items toward index 0, the size is not needed. This does assume that the given index is valid.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image182-1.png\" alt=\"1 function siftUp(array, index) 2 while index &gt; 0 and array[parent(index)] &lt; array[index] 3 exchange(array, index, parent(index)) 4 set index to parent(index).\" width=\"617\" height=\"72\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">With these two helper functions, we can now implement the methods to insert elements and remove the max-element from our priority queue. Before we move on though, let\u2019s think about the complexity of these operations. Each of these methods moves items up or down the depths of a binary tree. If the tree could remain balanced, then a traversal from the top to bottom or bottom to top should only require O(log n) operations, assuming that the tree is balanced.<\/p>\n<h4 class=\"import-Normal\">Insertion<\/h4>\n<p class=\"import-Normal\">Consider inserting the number 8 into the prior binary heap example. Imagine if we simply added that 8 in the array after the 2 (in position 6).<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.3%3A,0%20through%206.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image183-1.png\" alt=\"The same heap as the previous figure with an 8 added to the end position. This position is incorrect according to heap ordering. Click image for long description.\" width=\"883\" height=\"453\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.3<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">What can we now claim about the state of our binary heap? Subheaps starting at indexes 1, 3, 4, and 5 are all still valid subheaps because the heap property is preserved. In other words, our erroneous insertion of 8 under 4 does not alter the descendants of these 4 nodes. As a result, we could hypothetically leave these subheaps unaltered in our corrected heap. This leaves nodes at indexes 0 and 2. These are the two nodes that have had their descendants altered. The heap property between node indexes 2 and 6 no longer holds, so let us start there. If we were to switch the 4 and 8, we would restore the heap property between those two indexes. We also know that moving 8 into index 2 will not affect the heap property between indexes 2 and 5. If 2 was less than 4 and 4 was found to be less than 8, switching the 4 and 8 does not impact the heap property between indexes 2 and 5. Once the 4 and 8 are in the correct positions, we know that the subheap starting at index 2 is correct. From here, we simply perform the same operations on subsequent parents until the next parent\u2019s value is greater than the value we are trying to insert. Given that we are inserting 8 and our root node\u2019s value is 12, we can stop iterating at this point. The pseudocode below is descriptive but much simpler than practical implementations, which must consider precise data structures for storing the heap. This provides the general pattern for inserting into a binary heap regardless of the underlying implementation. We place the new element at the end of the heap and then essentially siftUp that element to the place that will preserve the heap property.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image184-1.png\" alt=\"1 function insert(heap, value) 2 Add value at the end of the heap 3 set n to last element in heap 4 while n is not heap.root and n.value &gt; n.parent.value 5 exchange n and n.parent within heap 6 set n to n.parent.\" width=\"609\" height=\"99\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Runtime of insertion is independent of whether the heap is stored as object references or an array. In either case, we have to compare n.value to n.parent.value at most O(log n) times. Note that, unlike the caveat included in binary search trees (where traversing an unbalanced tree may be as slow as O(n)), binary heaps maintain their balance by building each new depth level before increasing its depth. This ensures that an imbalanced binary heap does not occur. This fact guarantees that our insert operation is O(log n).<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">A specific implementation for insert with our array-based heap is provided below:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image185-1.png\" alt=\"1 function insert(array, value) 2 # place the element at the end and update size 3 set array[size] to value 4 siftUp(array, size) 5 set size to size + 1.\" width=\"614\" height=\"86\" \/><\/div>\n<h4 class=\"import-Normal\">Extraction<\/h4>\n<p class=\"import-Normal\">Extraction is the process of removing the root node of a binary heap. It works much the same way as insertion but in reverse. The general strategy is as follows.<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">To extract an element from the heap\u2026<\/p>\n<ol>\n<li class=\"import-Normal\">Extract the root element, and prepare to return it.<\/li>\n<li class=\"import-Normal\">Replace the root with the last element in the heap.<\/li>\n<li class=\"import-Normal\">Call heapify on the new root to correct any violations of the heap property.<\/li>\n<\/ol>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As an example, consider our corrected heap from before. If we overwrite our 12 (at index 0) with the last value from the array (4 at index 6), the result will be as follows in figure 9.5. Just as we saw with insertion, many of our subheaps still have the heap property preserved. In fact, the only two places where the heap property no longer holds are from indexes 0 to 1 and 0 to 2. If the value at the root is less than the maximum value of its two children, then we swap the root value and that maximum. We will continue this process of pushing the root value down until the current node is greater than both children, thus conforming to the heap property. In this case, we swap the 4 with the 8. The root node conforms to the heap property because its children are 7 and 4. The node with value 4 (now at index 2) only has one child (2 at index 5). It conforms to the heap property, and our extraction is complete.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.4%3A,0%20through%206.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image186.png\" alt=\"The same heap as the previous figure with 8 now in its correct position according to heap ordering. Click image for long description.\" width=\"873\" height=\"442\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.4<\/p>\n<\/div>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.5%3A%20Diagram%20of%20a%20binary%20tree%3A%20root%204%20(index%200)%20has%20children%207%20(index%201)%20and%208%20(index%202)%3B%20node%207%20has%20children%203%20(index%203)%20and%205%20(index%204)%3B%20node%208%20has%20a%20single%20left%20child%202%20(index%205).%20Below%20the%20tree%2C%20a%206%2Delement%20array%20shows%20the%20same%20values%20in%20level%20order%3A%204%2C%207%2C%208%2C%203%2C%205%2C%202%2C%20indexed%200%20through%205.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image187-1.png\" alt=\"The same heap as the previous figure after the max has been extracted. Click image for long description.\" width=\"868\" height=\"438\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.5<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As before, the pseudocode is much simpler than the actual implementation.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image188-1.png\" alt=\"1 function extract(heap) 2 set v to heap.root.value 3 set heap.root.value to heap.last.value 4 Delete heap.last.value 5 set n to heap.root 6 while n has children and n.value &lt; Max(n.left.value, n.right.value) 7 if Max(n.left.value, n.right.value) equals n.left.value 8 exchange n and n.left 9 set n to n.left 10 else 11 exchange n and n.right 12 set n to n.right 13 return v.\" width=\"627\" height=\"201\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The array-based implementation could use the heapify function to give the following code:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image189.png\" alt=\"1 function extract(array) 2 # save the max item to return 3 set maxItem to array[0] 4 5 # move the last item to the root, and update size 6 set array[0] to array[size - 1] 7 set size to size - 1 8 9 # now heapify the array from the root 10 heapify(array, 0, size) 11 12 return maxItem.\" width=\"609\" height=\"181\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">While accessing the max-element would only require O(1) time, updating the heap after it is removed requires a call to heapify. This function requires O(log n). While not constant time, O(log n) is a great improvement over our initial na\u00efve implementation ideas from the introduction. Our initial idea of sorting and then always copying moving elements up or down would have required O(n) operations to maintain our priority queue when inserting and removing elements. The max-heap greatly improves on these complexity estimates, giving O(log n) for both insert and extract.<\/p>\n<h3 class=\"import-Normal\">Heap Sort<\/h3>\n<p class=\"import-Normal\">Heap Sort presents an interesting use of a priority queue. It can be used to sort the elements of an array. Once insertion and extraction have been defined, Heap Sort becomes a trivial step. We first build the heap, then repeatedly extract the maximum element and put it at the end of the array. Much like Selection Sort, Heap Sort will find the extreme value, place it into the correct position, then find the extreme of the remaining values. The trick is in how we perceive the heap. If we model it using an array, we can then sort the values in place by extracting the maximum. The extraction makes the heap smaller by one, but arrays are fixed size and still have the extra space allocated at the end. This portion at the end of the array becomes our sorted portion. As we perform more extractions and move those extracted values to the end of the array, our sorted portion gets bigger. See the figure below for an example. Unlike Selection Sort, where finding that extreme value requires an O(n) findMax or findMin, heaps allow us to extract the extreme value and revise our heap in O(log n) time. We perform this operation O(n) times, resulting in an O(n log n) sorting algorithm. The following figure gives an example execution of the sorting algorithm:<\/p>\n<div class=\"textbox standard\">\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\">\n<tbody>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"7\" scope=\"colgroup\">heap<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\">\n<tbody>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"6\" scope=\"colgroup\">heap<\/td>\n<td style=\"width: 14.2857%;text-align: center\" scope=\"colgroup\">\u00a0s<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%;height: 30px\">\n<tbody>\n<tr style=\"height: 15px\">\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">12<\/td>\n<\/tr>\n<tr style=\"height: 15px\">\n<td style=\"height: 15px;width: 14.2857%;text-align: center\" colspan=\"5\" scope=\"colgroup\">heap<\/td>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"2\">sorted<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\">\n<tbody>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"4\" scope=\"colgroup\">heap<\/td>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"3\" scope=\"colgroup\">sorted<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\">\n<tbody>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"3\" scope=\"colgroup\">heap<\/td>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"4\" scope=\"colgroup\">sorted<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%;height: 30px\">\n<tbody>\n<tr style=\"height: 15px\">\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\">12<\/td>\n<\/tr>\n<tr style=\"height: 15px\">\n<td style=\"width: 14.2857%;height: 15px;text-align: center\" colspan=\"2\" scope=\"colgroup\">heap<\/td>\n<td style=\"width: 14.2857%;height: 15px;text-align: center\" colspan=\"5\" scope=\"colgroup\">sorted<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"grid aligncenter\" style=\"border-collapse: collapse;width: 50%\">\n<tbody>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\">2<\/td>\n<td style=\"width: 14.2857%;text-align: center\">3<\/td>\n<td style=\"width: 14.2857%;text-align: center\">4<\/td>\n<td style=\"width: 14.2857%;text-align: center\">5<\/td>\n<td style=\"width: 14.2857%;text-align: center\">7<\/td>\n<td style=\"width: 14.2857%;text-align: center\">8<\/td>\n<td style=\"width: 14.2857%;text-align: center\">12<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 14.2857%;text-align: center\" scope=\"colgroup\">h<\/td>\n<td style=\"width: 14.2857%;text-align: center\" colspan=\"6\" scope=\"colgroup\">sorted<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p class=\"import-Normal\">Figure 9.6<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Before we give the implementation of Heap Sort, we should also mention how to build the heap in the first place. If we are given an array of random values, there is no guarantee that these will conform to our requirements of a heap. This is accomplished by calling the heapify function repeatedly to build valid heaps starting at the deeper levels of the balanced tree up to the root. Below is the code for buildHeap, which will take an array of elements to be sorted and put them into the correct heap ordering:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image191-1.png\" alt=\"1 function buildHeap(array) 2 set size to length(array) 3 # move the index up to the root by counting down 4 for index from size\/2 to 0 5 heapify(array, index, size).\" width=\"615\" height=\"86\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">It might be unintuitive, but buildHeap is O(n) in its time complexity. At first glance, we see heapify, an O(log n) operation, getting called inside a loop that runs from size\/2 down to 0. This might seem like O(n log n). What we need to remember though is that O(log n) is a worst-case scenario for heapify. It may be more efficient. As we build the heap up, we start at position size\/2. This is because half of the heap\u2019s elements will be leaves of the binary tree located at the deepest level. As we heapify the level just before the leaves, we only need to consider three elements: the parent and its two leaf children. As heapify runs, the amount of work is proportional to the height of the subtree it is operating on. Only on the very last call does heapify potentially visit all log n of the levels of the tree. We will omit the calculation details, but it has been proven that O(n) gives a tighter bound on the worst-case time complexity of buildHeap.<\/p>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we are ready to implement Heap Sort. An implementation is provided below. Our O(n log n) complexity comes from calling heapify from the root every time we extract the next largest value. Another useful feature of this algorithm is that it is an <strong>in-place<\/strong> sorting algorithm. This means the extra space (auxiliary space) only consumes O(1) space in memory. So Heap Sort compares favorably to Quick Sort with a better worst-case complexity (O(n log n) vs. O(n<sup>2<\/sup>)), and it offers an improvement over Merge Sort in terms of its auxiliary space usage (O(1) auxiliary space vs. O(n)). We should note that Heap Sort may perform poorly in practice due to cache misses, since traversing a tree skips around the elements of the array.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image192.png\" alt=\"1 function heapSort(array) 2 # heap order the elements 3 buildHeap(array) 4 # repeatedly extract elements and place them in position 5 for index from (size - 1) to 1 6 set element to extract(array) 7 set array[index] to element.\" width=\"604\" height=\"113\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This section has provided an overview of heapSort and the concept of a heap more generally. Heaps are great data structures for implementing priority queues. They can be implemented using arrays or linked data structures. The array implementation also demonstrates an interesting example of embedding a tree structure into a linear array. The power and simplicity of heaps make them a popular data structure. One potential disadvantage of the heap is that merging two heaps might require O(n) operation. To combine these two heaps, we would need to create a new array, recopy the elements, and then call buildHeap, taking O(n) operations. In the next section, we will discuss a new data structure that supports an O(log n) <strong>union<\/strong> operation.<\/p>\n<h2 class=\"import-Normal\">Binomial Heaps<\/h2>\n<p class=\"import-Normal\">The <strong>binomial heap<\/strong> supports a fast union operation. When two heaps are given, union can combine them into a new heap containing all the combined elements from the two heaps. Binomial heaps are linked data structures, but they are a bit more complex than linked lists or binary trees. There is an interesting characteristic to their structure, which models the pattern of binary numbers, and combining them parallels binary addition. Binary numbers and powers of 2 seem to pop up everywhere in computer science. In this section, we will present the binomial heap and demonstrate how it can provide a fast union operation. Then we will see how many of the other operations on heaps can be implemented with clever use of the union function.<\/p>\n<h3 class=\"import-Normal\">Linked Structures of Binomial Heaps<\/h3>\n<p class=\"import-Normal\">To build our heap, we need to discuss two main structures. The first part is the <strong>binomial tree<\/strong>. Each binomial tree is composed of connected <strong>binomial nodes<\/strong>. The structure of a binomial tree can be described recursively. Each binomial tree has a value k that represents its degree. The degree 0 tree, B<sub>0<\/sub>, has one element and no children. A degree k tree, B<sub>k<\/sub>, has k direct children but 2<sup>k<\/sup> nodes in total. When the B<sub>k<\/sub> tree is constructed, the roots of two B<sub>k\u22121<\/sub> trees are examined. The largest root of the two trees is assigned as the root of the new tree, assuming a <strong>max-binomial-heap<\/strong>. The heap is then represented as a <strong>list of binomial trees<\/strong>. A collection of trees is known as a <strong>forest<\/strong>. The main idea of the binomial is that each heap is a list of trees, and to combine the two heaps, one just needs to combine all the trees of equal degree. To facilitate this, the trees are always ordered by increasing tree degrees. A few illustrations will help you understand this process a little better.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.7%3A,2%C3%972%5E2).\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image193-1.png\" alt=\"Examples of binomial trees with degrees given. Each degree starting at zero give the number of children of the root node of the tree. Each binomial tree contains 2 to the degree power nodes. Click image for long dsecription.\" width=\"922\" height=\"378\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.7<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Using these trees, a heap would then be a list of these trees. To preserve the max-heap property, any node\u2019s priority must be larger than its child. Below is an example binomial heap. Let\u2019s call this heap<sub>A<\/sub>:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.8%3A,no%20children%20(B0)\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image194.png\" alt=\"Example binomial heap with degree 0, degree 1, and degree 3 trees. Click image for long description.\" width=\"985\" height=\"332\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.8<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Notice that the maximum element is in B<sub>1<\/sub> tree of this heap. This illustrates that the actual max-heap element is one of the root nodes of trees in the list. Now we can make the connection to binary numbers. This heap will either have a tree of any given degree or not. This could be indicated by a 0 or 1. So the above heap has a degree 0 tree, a degree 1 tree, and a degree 3 tree. In binary with the bits correctly ordered, this would be 1011<sub>2<\/sub> or the number 11<sub>10<\/sub> in base 10. Suppose there is another heap, heap<sub>B<\/sub>, that we wish to merge with. This is given below:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.9%3A%20Diagram%20of%20a%20binomial%20heap%20labeled%20heapB%2C%20showing%20a%20root%20list%20of%20two%20binomial%20trees%20connected%20by%20a%20horizontal%20arrow%3A%2025%20(B1%2C%20one%20child%3A%2013)%20and%2017%20(B2%2C%20two%20children%3A%2014%20and%206%2C%20where%2014%20has%20its%20own%20child%204)\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image195-1.png\" alt=\"A second binomial heap with degree 1 and degree 2 trees. Click image for long description.\" width=\"967\" height=\"237\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.9<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This heap has trees for degrees 1 and 2. In binary, we could represent this pattern as 110<sub>2<\/sub> or the number 6<sub>10<\/sub> in base 10. We will soon look at how these heaps could be merged, but first let\u2019s consider the process of binary addition for these two binary numbers: 11 and 6. The figure below gives an example of the addition:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.10%3A%20Diagram%20showing%20binary%20place%20values%20and%20a%20binary%20addition%20example.%20Top%20table%20lists%20powers%20of%20two%20with%20their%20values%3A%202%E2%81%B4%3D16%2C%202%C2%B3%3D8%2C%202%C2%B2%3D4%2C%202%C2%B9%3D2%2C%202%E2%81%B0%3D1.%20Below%2C%20a%20binary%20addition%20is%20shown%3A%201011%20plus%200110%2C%20with%20carried%201s%20written%20above%20the%202%C2%B3%20and%202%C2%B2%20columns%2C%20giving%20a%20sum%20of%2010001.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image196.png\" alt=\"Diagram of binary addition for the number 11 and 6 represented in binary. The diagram show the power of 2 places and the carry from addition of lower places. Click image for long description.\" width=\"964\" height=\"255\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.10<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This diagram of binary addition also demonstrates how our trees need to be combined to create the correct structure for our unified trees. The following images will show these steps in action. First, we will merge the two lists into another list (but not a heap yet). This merge is similar to the merge operation in Merge Sort:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.11%3A,subtrees%20as%20before).\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image197-1.png\" alt=\"An intermediate stage of a binomial heap union. This represents the state of the heap list after a merge, but before resolving all the binomial trees. Click image for long description.\" width=\"955\" height=\"680\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.11<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Next, the algorithm will examine two trees at a time to determine if the trees are the same degree. Any trees that have an equal degree will be merged. Because the nodes are ordered by degree, we only need to consider two nodes at a time and potentially keep track of a carry node.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.12%3A,down%20to%2012.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image198-1.png\" alt=\"The algorithm considers pairs of trees and tries to determine if the need to be combined. Click image for long description.\" width=\"950\" height=\"351\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.12<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">These nodes are not equal in degree. We can move on.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.13%3A,down%20to%2012.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image199-1.png\" alt=\"The algorithm combines any two trees of equal degree. Here two trees of degree 2 would be merged. Click image for long description.\" width=\"979\" height=\"363\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.13<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we are considering two nodes of equal degree. These two B<sub>1<\/sub> trees need to become a B<sub>2<\/sub> tree.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.14%3A,of%20preceding%20it.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image200.png\" alt=\"The algorithm continues and combines two trees of degree 2 to form one degree 3 tree. Click image for long description.\" width=\"943\" height=\"351\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.14<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">After combining the B<sub>1<\/sub> trees, we now have two B<sub>2<\/sub> trees that need to be combined. This will be done such that the maximum item of the roots becomes the new root.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.15%3A,root%20node%2018.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image201-1.png\" alt=\"The algorithm combines two degree 3 trees. Click image for long description.\" width=\"931\" height=\"364\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.15<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Again, the \u201ccarry\u201d from addition means that we now have two B<sub>3<\/sub> trees to merge. This step creates a B<sub>4<\/sub> tree with 2<sup>4<\/sup> = 16 nodes. The final merged heap is below, with one B<sub>0<\/sub> node and one B<sub>4<\/sub> node:<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.16%3A,Has%20no%20children.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image202.png\" alt=\"Finally, the unioned heaps have 1 degree 0 tree and one degree 4 tree. Click image for long description.\" width=\"885\" height=\"350\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.16<\/p>\n<\/div>\n<h3 class=\"import-Normal\">Implementing Binomial Trees<\/h3>\n<p class=\"import-Normal\">To implement Binomial trees, we will need to create a node class with appropriate links. Again, we will use references, also known as pointers, for our links. A node\u2014and by extension, a tree\u2014can be represented with the BinomialTree class below. In this class, Data would be any entity that needed storing in the priority queue:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image203-1.png\" alt=\"1 Class BinomialTree 2 Data data 3 Integer priority 4 Integer degree 5 # links to other nodes 6 BinomialTree parent 7 BinomialTree sibling 8 BinomialTree child.\" width=\"623\" height=\"130\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">For the BinomialHeap itself, we only need a reference to the first tree in the forest. This simple pseudocode is presented below:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image204.png\" alt=\"1 class BinomialHeap 2 BinomialTree head.\" width=\"624\" height=\"44\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">As we progress toward a complete implementation, we will build up the operation that we need, working toward the union operation. Once union is implemented, adding or removing items from the heap can be implemented through the clever usage of union. For now, let\u2019s implement the combine and merge functions.<\/p>\n<h3 class=\"import-Normal\">Combining Two Binomial Trees<\/h3>\n<p class=\"import-Normal\">The combine function is given below. This simple function combines two B<sub>k\u22121<\/sub> trees to create a new B<sub>k<\/sub> tree. This function will make the first tree a child of the second tree. We will assume that tree1.priority is always less than or equal to tree2.priority.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image205-1.png\" alt=\"1 function combine(tree1, tree2) 2 set tree1.parent to tree2 3 set tree1.sibling to tree2.child 4 set tree2.child to tree1 5 set tree2.degree to tree2.degree + 1.\" width=\"616\" height=\"86\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The figure below shows how two B<sub>2<\/sub> trees would be combined to form a B<sub>3<\/sub> tree. This figure also identifies the parent, sibling, and child links for each node. Links that do not connect to any other node have the value null. This figure can help you understand the combine function. We need to maintain these links in a specific way to make the other operations function correctly. Notice that the children of the root are all linked together by sibling links, like a linked list\u2019s next reference.<\/p>\n<div class=\"textbox standard\">\n<div class=\"wp-nocaption aligncenter\"><a href=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/back-matter\/alt-text-long-description\/#:~:text=Figure%209.17%3A%20The%20diagram%20is%20split%20into%20two%20halves,vertical%20upward%20arrow%20pointing%20back%20to%20the%20root%2C%20node%2025.\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image206-1.png\" alt=\"Two degree 2 trees ready to be merged. The resulting degree 3 tree has 3 children. These children are a degree 0 tree, a degree 1 tree, and a degree 2 tree. Click image for long description.\" width=\"914\" height=\"363\" \/><\/a><\/div>\n<p class=\"import-Normal\">Figure 9.17<\/p>\n<\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Another interesting feature of binomial trees is that each tree of degree k contains subtrees of all the degrees below it. These are the children linked from the first child of the new tree. For example, the B<sub>3<\/sub> tree contains a B<sub>0<\/sub>, B<sub>1<\/sub>, and B<sub>2<\/sub> subtree in descending order. You can observe these in the figure above. This fact will come in handy when we implement the extract function for binomial heaps.<\/p>\n<h3 class=\"import-Normal\">Merging Heaps<\/h3>\n<p class=\"import-Normal\">Now that we can combine two trees to form a higher-degree tree, we should implement the mergeHeaps function. This will take both heaps and their forests of binomial trees and merge them. You can think of these \u201cforests\u201d as linked lists of binomial trees. Once these forests are merged, trees of equal degree will be adjacent in the list. This sets the stage for our \u201cbinary addition\u201d algorithm that will calculate the union of both heaps. The code for mergeHeaps is below:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image207-1.png\" alt=\"1 function mergeHeaps(heap1, heap2) 2 set tree1 to heap1.head 3 set tree2 to heap2.head 4 set newHeap to an instance of BinomialHeap 5 # if either heap is null, return the other 6 if tree1 equals null 7 return tree2 8 if tree2 equals null 9 return tree1 10 11 # set the heap's head to the lowest degree tree 12 if tree1.degree &lt;= tree2.degree 13 set newHeap.head to tree1 14 else 15 set newHeap.head to tree2 16 set current to newHeap.head 17 while (tree1 is not null) and (tree2 is not null) 18 if tree1.degree &lt;= tree2.degree 19 # update sibling links 20 set current.sibling to tree1 21 set current to current.sibling 22 # advance to tree1's next node 23 set tree1 to tree1.sibling 24 else 25 # if this is not the first node, update sibling links 26 set current.sibling to tree2 27 set current to current.sibling 28 # advance to tree2's next node 29 set tree2 to tree2.sibling 30 31 # tree1 or tree2 is null 32 # end of one list was reached 33 if tree1 equals null 34 set current.sibling to tree2 35 else 36 set current.sibling to tree1 37 38 return newHeap.head.\" width=\"624\" height=\"554\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">This may look a little difficult to follow, but the concept is simple. Starting with links to the lists of binomial trees, we first check to see if any of these are null. If so, we just return the other one. Afterward, we check which of the nonnull trees has the lowest degree and set our newHeap\u2019s head to this tree. The while-loop then appends the tree with the next smallest degree to the growing list. The loop continues until one of the two lists of trees reaches its end. After that, the remaining trees are linked to the list by the current reference, and the head of our merged list is returned. Notice that the sibling references serve the same role as the next pointers of a linked list.<\/p>\n<h3 class=\"import-Normal\">The Binomial Heap Union Operation<\/h3>\n<p class=\"import-Normal\">Now we will tackle the union function. This function performs the final step of combining two binomial heaps by traversing the merged list and combining any pairs of trees that have equal degrees. The algorithm is given below:<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image208-1.png\" alt=\"1 function union(heap1, heap2) 2 set newHeap to an instance of BinomialHeap 3 set newHeap.head to mergeHeaps(heap1, heap2) 4 if newHeap.head equals null 5 return newHeap 6 7 # create references to traverse the merged list 8 set previousTree to null 9 set currentTree to newHeap.head 10 set nextTree to newHeap.sibling 11 12 while nextTree is not null 13 # advance the traversal cases 14 if (currentTree.degree is not nextTree.degree) or 15 ((nextTree.sibling is not null) and 16 (currentTree.degree equals nextTree.sibling.degree)) 17 set previousTree to currentTree 18 set currentTree to nextTree 19 else 20 # combine the trees with equal degree by priority 21 if currentTree.priority &gt;= nextTree.priority 22 set currentTree.sibling to nextTree.sibling 23 # currentTree has higher priority 24 combine(nextTree, currentTree) 25 else 26 # first node? make sure to update the heap's head 27 if previousTree equals null 28 set newHeap.head to nextTree 29 else 30 set previousTree.sibling to nextTree 31 # nextTree has higher priority 32 combine(currentTree, nextTree) 33 set nextTree to currentTree.sibling 34 return newHeap.\" width=\"627\" height=\"498\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The union function begins by setting up a new, empty heap and then merging the two input heaps. Once the merged list of trees is generated, the algorithm traverses the list using three references (previousTree, currentTree, and nextTree). The code will advance the traversal forward if currentTree and nextTree have different degree values. Another case that moves the traversal forward is when nextTree.sibling has the same degree as currentTree and nextTree. This is because nextTree and nextTree.sibling will need to combine to occupy the k + 1 degree level. When a call to combine is needed, the algorithm checks which tree has the highest priority, and that tree\u2019s root becomes the root of the k + 1 tree.<\/p>\n<h3 class=\"import-Normal\">Time Complexity of Union<\/h3>\n<p class=\"import-Normal\">The union operation is completed, but now we should analyze its complexity. One of the main reasons for choosing a binomial heap was its fast union operation. How fast is it though? We will be interested in the time complexity of union. The algorithm traverses both heaps for the merge and the sequence combinations. This means that the complexity is proportional to the number of trees. We need to determine how many binomial trees are needed to represent all n elements of the priority queue. Recall that there are many parallels between binomial heaps and binary numbers. If we have 3 items in our heap, we need a tree of degree 0 with 1 item and a tree of degree 1, with 2 items. To store 5 items, we would need a degree 0 tree with 1 item, and a degree 2 tree with 4 items. Here we see that the binary representation of n indicates which trees of any given degree are needed to store those elements. A number can be represented in binary using a maximum number of bits proportional to the log of that number. So there are log n trees in a binomial heap with n elements. This means that the time complexity of union is bounded by O(log n). By similar reasoning, the time cost for finding the element with the highest priority is O(log n), the number of binomial trees in the heap.<\/p>\n<h3 class=\"import-Normal\">Inserting into a Binomial Heap<\/h3>\n<p class=\"import-Normal\">With union completed, we can see the benefit of this operation. Below is an implementation of insert using union. The union operation takes O(log n) time, and all other operations can be performed in O(1) time. This makes the time complexity for insert O(log n).<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image209-1.png\" alt=\"1 function insert(heap, data, priority) 2 # create a new heap 3 set newHeap to an instance of BinomialHeap 4 5 # create a tree node 6 set tree to an instance of BinomialTree 7 set tree.data to data 8 set tree.priority to priority 9 set tree.degree to 0 10 set tree.parent to null 11 set tree.sibling to null 12 set tree.child to null 13 14 # add degree 0 tree to heap 15 set newHeap.head to tree 16 17 # union the heap and the new heap to insert 18 return union(heap, newHeap).\" width=\"619\" height=\"270\" \/><\/div>\n<h3 class=\"import-Normal\">Extracting the Max-Priority Element<\/h3>\n<p class=\"import-Normal\">The priority queue would not be complete without a function to extract the maximum element from the heap. The extract function takes a bit more work, but ultimately extract executes in O(log n) time. The maximum priority element must be the root of one of the heap\u2019s trees. This function will find the maximum priority element and remove its entire tree from the heap\u2019s tree list. Next, the children of the max-element are inserted into another heap. With the two valid heaps, we can now call union to create the binomial heap that results from removing the highest priority element. This element can be returned, and the binomial heap will have been updated to reflect its new state. We note that in this implementation, there is a side effect of extract. This function returns the maximum priority element and removes it from the input heap as a side effect that modifies the input. Another approach would be to implement an accessMax function to find the maximum priority element and return it without updating the heap. This means that extracting the element would require a call to accessMax to save the element, and then extract would be called. We could also consider extracting part of the BinomialHeap class and avoid passing any heap as input.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image210.png\" alt=\"1 function extract(heap) 2 # first, find tree with max item 3 set previousTree to null 4 set currentTree to heap.head 5 if currentTree equals null 6 return null 7 8 set maxTree to currentTree 9 set maxPreviousTree to previousTree 10 11 while currentTree is not null 12 if currentTree.priority &gt; maxTree.priority 13 set maxTree to currentTree 14 set maxPreviousTree to previousTree 15 set previousTree to currentTree 16 set currentTree to currentTree.sibling 17 18 # connect previous tree to next tree in the heap 19 if maxPreviousTree equals null 20 # max is the first tree 21 set heap.head to maxTree.sibling 22 else 23 set maxPreviousTree.sibling to maxTree.sibling 24 25 # make a new heap for maxTree's children 26 set newHeap to an instance of BinomialHeap 27 set currentTree to maxTree.child 28 29 # reverse and add children to the new heap 30 while currentTree is not null 31 # save the next node 32 set nextTree to currentTree.sibling 33 # add trees to the front of the list, reverse the order 34 set currentTree.sibling to newHeap.head 35 set currentTree.parent to null 36 set newHeap.head to currentTree 37 set currentTree to nextTree 38 39 # now union modified heap and the heap of the max element's children 40 set heap to union(heap, newHeap) 41 return maxTree.\" width=\"621\" height=\"593\" \/><\/div>\n<h3 class=\"import-Normal\">Increase-Priority and Delete Operations<\/h3>\n<p class=\"import-Normal\">We will continue our theme of building new operations by combining old ones. Here we will present the delete operation. This operation will make use of extract and increasePriority, which we will develop next. Creating the increasePriority function will rely on the parent points that we have been maintaining. When the priority of an element is increased, it may need to work its way up the tree structure toward the root. The following code gives an implementation of increasePriority. We assume for simplicity that we already have a link to the element whose priority we want to increase. The element with the highest priority moves up the tree just like in the binary heap\u2019s siftUp operation.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image211-1.png\" alt=\"1 function increasePriority(heap, tree, newPriority) 2 if tree.priority &gt; newPriority 3 # do nothing if the new priority is less than the old. 4 return 5 6 set tree.priority to newPriority 7 set currentTree to tree 8 set parentTree to tree.parent 9 while (parentTree is not null) and (currentTree.priority &gt; parentTree.priority) 10 # exchange the data and priority of the current and parent trees 11 set temporaryData to parentTree.data 12 set parentTree.data to currentTree.data 13 set currentTree.data to temporaryData 14 15 set temporaryPriority to parentTree.priority 16 set parentTree.priority to currentTree.priority 17 set currentTree.priority to temporaryPriority 18 19 # move references up the tree toward the root 20 set currentTree to parentTree 21 set parentTree to parentTree.parent.\" width=\"619\" height=\"295\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">Now we can implement delete very easily using the MAX special value. We increase the element\u2019s priority to the maximum possible value and then call extract. An implementation of delete is provided below. Again, we assume that a link to the element we wish to delete is provided.<\/p>\n<div class=\"wp-nocaption aligncenter\"><img class=\"aligncenter\" src=\"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-content\/uploads\/sites\/57\/2023\/08\/image212-1.png\" alt=\"1 function delete(heap, tree) 2 increasePriority(heap, tree, MAX) 3 extract(heap).\" width=\"617\" height=\"58\" \/><\/div>\n<p class=\"import-Normal\" style=\"text-indent: 36pt\">The time complexity of delete is derived from the complexity of increasePriority and extract. Each of these requires O(log n) time.<\/p>\n<h3 class=\"import-Normal\">A Note on the Name<\/h3>\n<p class=\"import-Normal\">Before we close this chapter on priority queues, we should discuss why these are called binomial heaps. The name \u201cbinomial heap\u201d comes from a property that for a binomial tree of degree k, the number of nodes at a given depth d is k <em>choose<\/em> d. This is written as [latex]{\\large (k \\;d) = \\frac{k!}{d!(k-d)!}}[\/latex]<\/p>\n<h2 class=\"import-Normal\">Summary<\/h2>\n<p class=\"import-Normal\">In this chapter, we explored one of the most important abstract data types: the priority queue. This data structure provides a collection that supports efficient insert and remove operations with the added benefit of removing elements in order of priority. We looked at two important implementations. One implementation used an array and created a binary heap. We also saw that this structure can be used to implement an in-place O(n log n) sorting algorithm by simply extracting elements from the queue and placing them in the sorted zone of the array. Next, we explored the binomial heap\u2019s implementation. This data structure provides an O(log n) union operation. Though the implementation of binomial heaps seems complex, there is an interesting and beautiful simplicity to its structure. Our union algorithm also draws parallels to the addition of binary numbers, making it an interesting data structure to study. Any student of computer science should understand the concept of priority queues. They form the foundation of some interesting algorithms. For example, chapter 11 on graphs will present an algorithm for a minimum spanning tree that relies on an efficient priority queue. The minimum spanning tree is the backbone of countless interesting and useful algorithms. Hopefully, by now, you are beginning to see how data structures and algorithms build on each other through composition.<\/p>\n<p>&nbsp;<\/p>\n<div class=\"textbox textbox--exercises\">\n<header class=\"textbox__header\">\n<h2 class=\"textbox__title\">Exercises<\/h2>\n<\/header>\n<div class=\"textbox__content\">\n<ol class=\"legal\">\n<li class=\"import-Normal\">Implement Heap Sort on arrays in the language of your choice. Revisit your work from chapter 3 on sorting. Using your testing framework, compare Heap Sort, Merge Sort, and Quick Sort. Which seems to perform better on average in terms of speed? Why would this be the case on your machine?<\/li>\n<li class=\"import-Normal\">What advantages would Heap Sort have over Quick Sort? What advantages would Heap Sort have over Merge Sort?<\/li>\n<li class=\"import-Normal\">Extend your heap implementation to use references to data records with a priority variable rather than just an integer as the priority.<\/li>\n<li class=\"import-Normal\">Implement both binomial heaps using linked structures and binary heaps using an array implementation. Using a random number generator, create two equal-sized heaps, and try to merge them. Try the merge with binomial heaps, and get some statistics for the merge speed. Compare with the merge speed of binary heaps with integers. Repeat this process several times to explore how larger n affects the speed of the rival heap merge algorithms. The results may not be what you expect. How might caches play a role in the speed of these algorithms?<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox textbox--key-takeaways\">\n<header class=\"textbox__header\">\n<h2 class=\"textbox__title\">References<\/h2>\n<\/header>\n<div class=\"textbox__content\">\n<p class=\"import-Normal hanging-indent\">Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. <em>Introduction to Algorithms<\/em>, 2nd ed. Cambridge, MA: The MIT Press, 2001.<\/p>\n<p class=\"import-Normal hanging-indent\">Vuillemin, Jean. \u201cA Data Structure for Manipulating Priority Queues.\u201d <em>Communications of the ACM<\/em> 21, no. 4 (1978): 309\u2013315.<\/p>\n<\/div>\n<\/div>\n","protected":false},"author":13,"menu_order":9,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":3,"_links":{"self":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapters\/313"}],"collection":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/wp\/v2\/users\/13"}],"version-history":[{"count":18,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapters\/313\/revisions"}],"predecessor-version":[{"id":980,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapters\/313\/revisions\/980"}],"part":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapters\/313\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/wp\/v2\/media?parent=313"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/pressbooks\/v2\/chapter-type?post=313"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/wp\/v2\/contributor?post=313"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/pressbooks.palni.org\/anopenguidetodatastructuresandalgorithms\/wp-json\/wp\/v2\/license?post=313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}