Bifurcated Heap Implementation of Priority Queues
In previous chapters we learned about FIFO (first in first out).FIFO) data structure: queue (Queue). There is a variant of the queue called "priority queue" (Priority Queue). The outgoing queue of the priority queue (DequeueThe operation is the same as queuing, in that it takes the elements out of the queue from the head of the queue. However, within the priority queue, the order of the elements is determined by the "priority": high priority elements are placed at the head of the queue, while low priority elements are placed at the back. Thus, the priority queue entries (Enqueue) The operation is a bit more complicated, requiring elements to be placed as far to the front of the queue as possible based on priority. We will find the priority queue to be a useful data structure for the graph algorithm we will learn in the next section.
It is natural to think of using sorting algorithms and queuing methods to implement prioritized queues. However, the time complexity of inserting an element into a list isO(n), the time complexity of sorting the list isO(nlogn). We can reduce the time complexity in other ways. A classic way to implement a prioritized queue is to use a binary heap (Binary Heap). A binary heap keeps both the entry and exit complexity of a prioritized queue in theO(logn)。
The interesting thing about a binary heap is that it is logically structured like a binary tree, but is implemented as a non-nested list. There are two types of binary heaps: the one with always the smallest key at the head of the queue is called the "smallest heap".min heap), and conversely, the key value that is always the largest at the top of the queue is called the "largest heap (max heap)". In this section we use the minimal heap.
Bifurcated heap operations
The basic operations of a binary heap are defined as follows:
-
BinaryHeap(): Create an empty binary heap object -
insert(k): Add the new element to the heap -
findMin(): return the smallest item in the heap, the smallest item remains in the heap -
delMin(): Returns the smallest item in the heap and removes it from the heap. -
isEmpty(): Returns whether the heap is empty -
size(): return the number of nodes in the heap -
buildHeap(list): create a new heap from a list of nodes
The code shown below is an example of a binary heap. You can see that no matter which order we add the elements to the heap, the smallest element is removed each time. We are going to implement this process next.
from import BinHeap bh = BinHeap() (5) (7) (3) (11) print(()) print(()) print(()) print(())
For a better implementation of the heap, we use a binary tree. We must always keep the binary tree "balanced" by keeping the operations on a logarithmic scale. The root node of a balanced binary tree has the same number of children as the left and right subtrees. In the heap implementation, we use the structure of a "full binary tree" to approximate "balance". A complete binary tree is a tree in which every internal node is maximized, except for the last level, which can be missing only a few nodes on the right side. Figure 1 shows a complete binary tree.
Figure 1: Complete binary tree
What's interesting is that we can implement the full tree with a single list. We don't need to use nodes, references or nested lists. This is because for a complete binary tree, if a node is subscripted as p in the list, then its left child is subscripted as 2p and its right node is 2p+1. When we want to find the parent of any node, we can just use python's integer division. If the node has a subscript in the list ofn, then the parent node subscript isn//2. A list representation of a fully binary tree and tree is shown in Figure 2. Note the relationship between 2p and 2p+1 between parent and child nodes. The list representation of a complete tree combines the properties of a complete binary tree to allow us to efficiently traverse a complete tree using simple math. It also allows us to efficiently implement binary heaps.
The nature of the heap order
The way we store elements in the heap relies on the heap order. By heap order, we mean that any node x in the heap has a parent p whose key value is less than or equal to x's key value. Figure 2 shows a complete binary tree with the heap order property.
Figure 2: Complete tree and its list representation
Implementation of binary heap operations
Next we construct the binary heap. Because a list can be used to hold the data for the heap, the constructor only needs to initialize a list and acurrentSizeListing 1 shows the python code for constructing a binary heap. Notice that theheaplistis not used, but we keep it for the convenience of using integer division later in the code.
Listing 1
class BinHeap:
def __init__(self):
= [0]
= 0
What we're going to accomplish next isinsertmethod. First of all, in order to satisfy the "complete binary tree" property, the new key value should be added to the end of the list. However, simply adding the new key to the end of the list obviously does not fulfill the heap order. However, we can re-satisfy the heap order by comparing the parent node with the newly added element. If the newly added element is smaller than the parent node, it can swap places with the parent node. Figure 3 shows a series of swap operations to "float" the newly added element to the correct position.
Figure 3: The new node "floats" to its correct position.
When we "float" an element, we want to make sure that the new node is in the same heap order as its parent and other siblings. Of course, if the new node is very small, we still need to swap it to other layers. In fact, we need to keep swapping until we reach the top of the tree. listing 2 shows the "float" method, which "floats" a new node to its correct position to satisfy the heap order. This is a good example of what we saw earlier inheadlistThe significance of the element 0 that is not used in the This allows us to calculate the parent of any node just by doing a simple division, dividing the subscript of the current node by 2.
In Listing 3, we've been able to write theinsertmethod's code.insertA large part of the work inside is done bypercUpfunction accomplishes this. When a new node is added to the tree, a call to thepercUpIt will be possible to put the new node in the correct position.
Listing 2
def percUp(self,i):
while i // 2 > 0:
if [i] < [i // 2]:
tmp = [i // 2]
[i // 2] = [i]
[i] = tmp
i = i // 2
Listing 3
def insert(self,k): (k) = + 1 ()
We've already written it.insertmethod, then come back to thedelMinMethod. Heap order requires that the root node is the smallest element in the tree, so it is easy to find the smallest term. What is more difficult is how to maintain the heap structure and heap order after removing the elements of the root node, we can do it in two steps. First, replace the root node with the last node. Removing the last node maintains the nature of the heap structure. Such a simple replacement still destroys the heap order. The second step is to "sink" the new node to restore the heap order. Figure 4 shows a series of swap operations to "sink" the new node to the correct position.
Figure 4: Root node sinking after replacement
To maintain heap order, we need to "sink" the new root node along a path until it is smaller than both children. When choosing the sinking path, if the new root node is larger than a child node, then the smaller child node will be exchanged with it. listing 4 shows the required sinking path for the new node.percDowncap (a poem)minChildmethod's code.
Listing 4
def percDown(self,i):
while (i * 2) <= :
mc = (i)
if [i] > [mc]:
tmp = [i]
[i] = [mc]
[mc] = tmp
i = mc
def minChild(self,i):
if i * 2 + 1 > :
return i * 2
else:
if [i*2] < [i*2+1]:
return i * 2
else:
return i * 2 + 1
Listing 5 shows thedelMinThe code for the operation. You can see that the more troublesome areas are handled by a helper function, thepercDown。
Listing 5
def delMin(self): retval = [1] [1] = [] = - 1 () (1) return retval
The last part of the binary heap is finding a way to generate a "heap" from an unordered list. The first thing that comes to mind is to insert each element of the unordered list into the heap in turn. For an ordered list, we can use a binary search to find the right position, and then insert the key into the heap at the next position, with a time complexity ofO(logn). Also inserting an element into the list requires moving some other elements of the list to make room for the new node, with a time complexity ofO(n). Therefore, the use ofinsertThe total overhead of the method isO(nlogn). In fact, we can just generate the entire list into a heap, keeping the total overhead atO(n)Listing 6 shows the operation of generating a heap.
Listing 6
def buildHeap(self,alist):
i = len(alist) // 2
= len(alist)
= [0] + alist[:]
while (i > 0):
(i)
i = i - 1
Figure 5: Generating a binary heap from the list [ 9, 6, 5, 2, 3]
Figure 5 illustrates the use of thebuildHeapmethod takes the very first tree[ 9, 6, 5, 2, 3]The swap operation done when a node in the tree is moved to the correct position. Even though we start in the middle of the tree and work back to the root node, thepercDownmethod ensures that the largest child node is always "sunk". Since a heap is a fully binary tree, any node in the middle is a leaf node and therefore has no children. Note that wheni=1When we start sinking from the root node, this requires a large number of swap operations. As can be seen, the two trees on the far right of Fig. 5, first 9 are removed from the root node position, and after moving to the next level of the hierarchypercDownFurther checking its children at this point ensures that it descends until it can't descend any further, i.e., it descends to the correct position. A second swap is then performed, between 9 and 3. Since 9 has moved to the lowest level of the tree, no further swapping is possible. It is helpful to compare the series of swaps performed in the list representation with the tree representation shown in Figure 5.
i = 2 [0, 9, 5, 6, 2, 3] i = 1 [0, 9, 2, 6, 5, 3] i = 0 [0, 2, 3, 6, 5, 9]
The code shown below is an implementation of a fully binary heap.
def insert(self,k):
(k)
= + 1
()
def percDown(self,i):
while (i * 2) <= :
mc = (i)
if [i] > [mc]:
tmp = [i]
[i] = [mc]
[mc] = tmp
i = mc
def minChild(self,i):
if i * 2 + 1 > :
return i * 2
else:
if [i*2] < [i*2+1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = [1]
[1] = []
= - 1
able to do sth. withinO(n)The ability to generate a binary heap with the overhead of a binary heap may seem a bit implausible, and its proof is beyond the scope of this book. However, it's important to understand the benefits of usingO(n)The key to the overhead of being able to generate a heap is becauselognfactor is based on the height of the tree. And for thebuildHeapFor many operations in the tree, the height of the tree is higher than the height of thelognBe small.