Advanced algorithms and data
structures
Week 5 lecture notes by
Based on lecture slides by
Copyright By PowCoder代写 加微信 powcoder
Faculty of Information Technology August 24, 2021
1 Priority Queues . . . .
2 BinaryHeaps . . . . .
3 Binomial Heaps . . . .
…………………………………….. 2 …………………………………….. 2 …………………………………….. 4 …………………………………….. 4 …………………………………….. 6 …………………………………….. 8
3.1 Binomial trees
3.2 Binomial heaps
3.3 Representation
3.4 Binomialheapoperations ……………………………….. 9
3.4.1 Merge…………………………………….. 9
3.4.2 Extract-min …………………………………. 14
3.4.3 Decrease-key ………..
3.4.4 Delete……………
3.4.5 Insert……………
3.5 Summary ………………
……………………….. 16 ……………………….. 17 ……………………….. 18 ……………………….. 18
1. PRIORITY QUEUES
1 Priority Queues
Using disjoint-sets we are able to divide elements within our set into subsets (equivalence classes) according to a given equivalence relation, but these are not the only interesting relations we might want to apply to our set. For instance, imagine you are tasked with scheduling a set of documents to be printed by a single printer. Some of the documents may contain a large number of pages and it might be desirable to print them last since they will require more time than the smaller jobs, or perhaps one of the documents is very important and so should be printed first. It should be obvious that this task – which arises naturally in many more interesting contexts – requires some assignment of priorities to the documents that dictate the order in which they will be printed. To achieve this we could assign a number, or key from [1, n] to each of the documents and decide that those documents assigned low numbers should be given precedence over those with higher numbers. In other words, if we select two elements from our set with keys α and β we simply determine if α < β in order to determine which of the two documents should be printed first. However, this relation (<) is not an equivalence relation (return to lecture 4 to double check this) and so we clearly need to develop a different kind of data structure to handle this problem.
You should recall from your previous studies that the problem above is most elegantly abstracted using priority queues, which in the broadest sense simply assign a priority to the elements in a set such that the element with the highest priority is served first. In addition, priority queues support several operations, which can dependent on the application, but typically one might need to:
• Insert a new element into the queue.
• Identify the element with the highest priority.
• Extract the element with the highest priority.
• Alter the priority of an existing element in the queue.
Hopefully it is clear how a priority queue supporting such operations could be used to solve scheduling problems like contrived example above, but you should also recall that they can be used for sorting (heap sort), and feature prominently in many algorithms such as Prim’s and Dijkstra’s. Having defined the abstract notion of a priority queues we now turn our attention to their efficient implementation using heaps. In fact heaps are so commonly used to realise priority queues that the terms are often used interchangeably and hereafter our discussion will focus entirely on variants of the heap data-structure.
2 Binary Heaps
You are likely already familiar with a common heap variant known as a binary heap, but we will briefly review them here as they will serve as a good comparison point for the mergable variants that will occupy our focus for weeks 5 and 6.
Each element in our heap is represented by a node in the tree, which has associated with it both a payload and a key. The order property above describes a min-heap1 where the nodes with the smallest keys are assigned the highest priority. Furthermore, you should recall that min-heaps support the following operations:
• insert: Insert a new element (containing a key and an associated payload) into the heap.
• min: Identify the minimum element in the heap.
• extract-min: Identify and remove the minimum element in the heap.
1We could equally consider max-heaps where the nodes with the largest keys are assigned the highest priority, but we will restrict
ourselves to min-heaps here since translation between the two is not difficult.
Definition 1: Binary heaps
A binary heap is a binary tree that maintains two additional properties:
1. Structure: A binary heap is a complete binary tree, i.e. every level is full except possibly the last, which is always filled left-to-right.
2. Order (min-heap): The key of every node is less than or equal (≤) to the keys of its children.
2. BINARY HEAPS
• decrease-key: Decrease the key of an existing element in the heap.
Example 1: Binary heaps
Below is a binary (min-)heap containing 10 nodes. We can see that this heap satisfies the structure property as all the levels except the last (the leaf level) are completely filled. In addition, we can see that the order property is maintained as the key of every node is less than or equal that of its children.
Recall that due to the regularity of binary heaps we can actually represent them using an array rather than
explicitly representing binary tree itself. The array for this example can be seen below and for an element at
position i its left child is stored at position 2i, its right child is stored at position 2i + 1, and its parent is in
position i . Note that if any of the previous formulas yield a position outside the bounds of the array this 2
indicates that the corresponding element does not exist. For instance, the element H has no right child as indicated by the fact that 2i + 1 = 2(5) + 1 = 11.
1 2 3 4 5 6 7 8 9 10
ABEFHKLMTX
Binary heaps enable us to efficiently realise the aforementioned operations and the time-complexity of these opera- tions is summarised in table 1. To complement these results the fact that all these operations can be implemented using simple array manipulations - which are incredibly fast on most systems - makes a binary heap an incredibly practical data structure with a wide range of applications.
make-new-heap
extract-min
decrease-key
Binary heap
O(1) O(log N ) O(log N ) O(log N )
O(logN) worst-case O(1) amortized
Table 1: The worst case time complexity of binary heap operations. Note that the delete operation is usually implemented by simply calling a decrease-key followed by an extract-min, which is why it was omitted from the earlier list of operations.
If our heap only needs to support the operations listed in table 1 then binary heaps are typically a good choice2. However, what if we were to require an additional operation merge that simply merges two distinct heaps into one, are binary heaps able to implement this operation efficiently?
Let’s consider two binary heaps H1 and H2 that contain N elements each. We know that both H1 and H2 will actually be represented using two arrays each containing N elements and that representing the merged heap H will require an array of size 2N. To complete the merge we need to copy the elements of H1 and H2 to this larger array in a such a way that the resulting array corresponds to the a valid representation of H. But clearly just the act of
2We will see later that there are some applications that only require these operations where binary heaps do not lead to the optimal solution.
3. BINOMIAL HEAPS
copying these elements to our new array requires O(N) time and we have yet to account for any of the comparisons necessary to determine the order in which this copying should occur.
When compared to the other binary heap operations merge is computationally expensive and we are left to ponder an interesting question. Is possible to design a data structure that supports a more efficient implementation of the merge operation without compromising on the computational cost of the other operations? As we shall soon see this is indeed possible and in pursuit of this goal we will eventually arrive at a heap capable of outperforming binary heaps in particular applications.
3 Binomial Heaps 3.1 Binomial trees
In a binary heap we maintain a complete binary tree to preserve an O(log(N)) bound on the height of the heap. We would like to leverage a similar idea when designing our new heaps however, we will use a binomial trees instead of a binary ones.
Definition 2: Binomial trees
We define binomial trees recursively:
• The binomial tree of order 0 - denoted B0 - is a singleton node.
• The binomial tree of order 1 - denoted B1 - is constructed from two B0 trees, by making one the child of the other.
• The binomial tree of order 2 - denoted B2 - is constructed from two B1 trees, by making one the child of the other.
• and so on...
Figure 1: The binomial trees of order 0, 1, 2 and 3 are denoted by B0, B1, B2 and B3 respectively.
Binomial tree properties
A binomial tree of order k (Bk) has the following properties,
1. Bk contains 2k nodes.
2. Bk has height k.
3. The root of Bk has k subtrees as children.
4. Deleting the root node of Bk yields k independent lower order binomial trees Bk−1, Bk−2, ..., B0.
5. The number of nodes at any given depth d is given by the binomial coefficient k = k! , that is d (k−d)!d!
‘k-choose-d’.
3. BINOMIAL HEAPS
We will formally prove the majority of these properties during tutorials, but they all, bar the last follow rather straightforwardly from the definition of binomial trees. Let’s consider each of them in turn.
Properties 1 and 2 can be be intuited by simply considering the recursive definition of binomial trees and noting that B0 by definition contains 20 = 1 node and has height 0. For instance, B1 is constructed by making one B0 tree the child of another and so must contain 2 × 1 = 21 nodes and have height 1. Similarly, B2 is constructed by making one B1 tree the child of another and so must contain 2 × 2 = 22 = 4 nodes and have height 2. This reasoning can easily be formalised into inductive proofs to show that these patterns hold true for a binomial tree of any order as claimed.
Similarly properties 3 and 4 become obvious once one examines a binomial tree. The root of a B0 tree has 0 subtrees as it is a singleton node, the root of a B1 tree has 1 B0 tree as its subtree, which in turn implies that the root of a B2 tree has two subtrees; one B1 tree and one B0 tree that belonged to the original B1 tree. Finally, property 5 is responsible for the name binomial tree and an inductive proof of this will be explored in tutorials.
3. BINOMIAL HEAPS
3.2 Binomial heaps
Now that we have a solid grasp of binomial trees we’re ready to define the first of two efficiently mergable heaps that we will explore in the unit.
The two properties of binomial heaps are very similar to those of the more familiar binary heaps. We still require that the nodes in any tree in the heap maintain (min-)heap order, however now the heap can consist of multiple trees and they are binomial trees instead of a complete binary tree.
Definition 3: Binomial heap
A binomial heap is a forest - or a set - of binomial trees that satisfies two properties:
• Structure: There is at most one binomial tree of any given order in the heap.
• Order: Each binomial tree in the heap satisfies the heap property - i.e. the key of any node in the heap is less than or equal to (≤) the keys of its children.
Example 2: Binomial heap
Below is an example of a binomial heap. Notice that it is simply a collection of binomial trees where each order of tree can appear at most once. In this instance, the heap contains: one B0 tree, one B1 tree, and one B4 tree, while all the other orders (2, 3, 5, ...) of binomial trees are absent. Moreover, we can see that the keys of the nodes in each of the trees present are ordered in a min-heap fashion as required by the order property.
The properties of binomial trees mentioned in section 3.1 are interesting in their own right, but they also induce some attractive properties in binomial heaps.
Binomial heaps properties
For a binomial heap containing N elements the following hold:
1. The ‘1’s in the minimal binary representation of N dictate which order of binomial trees are present in
2. There are at most ⌊log2(N)⌋ + 1 binomial trees in the heap.
3. The height of any tree in the heap is ≤ ⌊log2(N)⌋
4. The node with the minimum key in the entire heap will be one of the root nodes of the trees in the heap.
3. BINOMIAL HEAPS
Example 3: Binomial heap properties
The first of the binomial heap properties deserves closer examination, so let’s delve into its origins. Recall that a binomial tree of order k (Bk) contains exactly 2k nodes and that a binomial heap contains at most a single copy of any binomial tree of a given order. Therefore the N nodes that make up our heap are divided into groups of powers of 2, with each power occurring at most once. But this is equivalent to expressing N as a sum of powers of 2 where the coefficient of each power is either 0, or 1, which of course yields the binary representation of N!
If we consider the heap below we can see that it contains N = 19 nodes, which in binary can be represented 12345
as 1 0 0 1 1 . This indicates that the trees B4, B1, and B0 are present in the heap, which contain 24, 21, and 20 nodes respectively. Note that 010011 would be an equally valid binary representation for 19 however, we can ignore the leading zeros since the minimal binary representation of 10011 - with 1 in the most significant bit - is sufficient to determine which trees are and aren’t present in the heap.
The fact that Bk contains 2k nodes (along with the structure property of binomial heaps) naturally yields this useful binary representation of our heap and through it we can easily derive properties 2 and 3. For any given N there are ⌊log2(N)⌋+1 bits in the minimal binary representation of N, and so by property 1 there are at most ⌊log2(N)⌋+1 binomial trees in a heap of N elements. Further, the highest order binomial tree present in a heap of N nodes must be B⌊log2(N)⌋, (no +1 as B0 is the lowest order tree possible) which we know to have height ⌊log2(N)⌋. Since the height of binomial trees increases monotonically with the order of the tree, B⌊log2(N)⌋ must be the tallest tree in our heap and we conclude that the height of every tree in our heap is ≤ ⌊log2(N)⌋.
Finally, property 4 follows simply from the fact that each binomial tree in our heap is min-heap ordered so that the minimum key must be that of the root node for every tree. Taking the minimum key over all of the root nodes therefore yields the minimum key in the heap.
3. BINOMIAL HEAPS
3.3 Representation
Now that we’ve established the conceptual notion of a binomial heap, we need to examine their practical imple- mentation as this will influence the efficiency with which we can realise operations on the heap.
Earlier in section 1 we discussed how the array representation of binary heaps fundamentally limits them when we require the ability to merge two heaps. Thus, it should be clear that our implementation of binomial heaps cannot be array based if we are to support efficient merging. Instead we must fall back to a more explicit tree representation and use a collection of linked nodes that each store a collection of data and pointers.
Binomial heap nodes
Any given node x in a binomial heap stores the following information:
• A key (x.key) that is used to order the node within the heap.
• An optional payload (x.payload) that is auxiliary information associated with the node i.e. the informa- tion that is being stored within the node and ordered by the key.
• A parent pointer (x.parent).
• A pointer to the nodes left most child (x.child) to enable traversal to the children list.
• A pointer to the node’s right sibling (x.sibling).
• The degree of the node (x.degree), which is the number of children that the node has.
Figure 2: A depiction of a binomial heap node.
The root nodes of all the trees in the heap are connected via the sibling pointers and form a linked list that we refer to as the root list. To provide access to the head of this list we maintain a pointer which we’ll simply refer to as head. The child pointers of each node in the root list then provide access to the remaining nodes in their respective trees.
Example 4: Binomial heap representation
Below is a binomial heap that consists of 3 binomial trees: one B0 tree, one B2 tree, and one B3 tree, and below it is a depiction of the explicit tree representation. Notice that the head pointer provides access to the root list and that the child list at each level of a given tree can be accessed via the child pointer. In addition, each node stores its degree, or the number of children it has so that we are able to access the order of the binomial tree rooted at that node in constant time. Finally, observe that the binomial trees are kept in monotonically increasing order in the root list. We shall soon see that maintaining this order is important when attempting to implement operations on the heap efficiently.
3. BINOMIAL HEAPS
Before continuing it is important to note that the representation given above is not the only feasible one for binomial heaps and it is a good exercise to ponder the advantages and disadvantages of our implementation.
3.4 Binomial heap operations
We motivated our development of binomial heaps with our need for a heap that is efficiently mergable so let’s see if we have achieved our goal.
3.4.1 Merge
To merge two binomial heaps H1 and H2 into a single binomial heap H we will need to merge the constituent trees in a manner that ensures that H is a valid binomial heap. With this in mind it is natural to begin by determining how to merge two binomial trees and in particular we need to determine how to merge two trees of the same order.
Merging binomial trees
Consider two binomial trees of order k (order 3 in figure 3). We know that making the root of one of these trees the child of the other will yield a single Bk+1 (B4) tree, but the order of this merging is not arbitrary in general. Instead we want to combine the trees so that the resulting tree is still min-heap ordered. That is, the root with the larger key must become the child of the root with the smaller key, as shown in figure 3 below. When merging in this way only the root gains a new child whose key is guaranteed to be less than or equal to that of the root, thus maintaining the min-heap order as desired.
Figure 3: Merging two min-heap ordered B3 trees so that the resulting B4 tree remains min-heap ordered.
3. BINOMIAL HEAPS
Example 5: Merging binomial trees
Conceptually merging two binomial trees is rather simple, but in preparation for our complexity analysis of this operation we need to look a little closer at the operations required. Suppose we are trying to merge the two B2 trees rooted at nodes with keys 43 and 21 as shown below. In this case we need to perform the following operations.
Figure 4: First make the tree with the smaller root 21 (call it r1) the parent of the tree with the larger root 43 (call it r2). This requires setting the parent pointer of r2.
Figure 5: Next we need to add r2 to the child list for r1 by setting the sibling pointer of r2 so that its right sibling is the (previously) left-most child of r1.
Figure 6: Now update the child pointer of r1 so that it points to r2 which is now the left-most child.
3. BINOMIAL HEAPS
Figure 7: Finally, we need to increment the degree of r2 as we have just added a child to it.
The previous operations simply require updating a cons
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com