程序代写 FIT3155 S1 2022, Monash University) Binomial heaps 1 / 36

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act). The material in this communication may be subject to copyright under the Act. Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act. Do not remove this notice
(FIT3155 S1 2022, Monash University) Binomial heaps 1 / 36

Prepared by: [ ] Extended by:
FIT3155: Advanced Algorithms and Data Structures
Week 5: Binomial heap and its amortized analysis
Faculty of Information Technology, Monash University
(FIT3155 S1 2022, Monash University) Binomial heaps 2 / 36

What is covered in this lecture?
Binomial heap and its amortized analysis
Original reference
, A Data Structure for Manipulating Priority Queues Communications of the ACM, 21(4) 309-314. [link]
(FIT3155 S1 2022, Monash University) Binomial heaps 3 / 36

Source material and recommended reading
Weiss, Data Structures and Algorithm Analysis (Chapters 6.8, 11.1, 11.2)
Cormen et al., Introduction to Algorithms (Chapter 19) [link]
(FIT3155 S1 2022, Monash University) Binomial heaps 4 / 36

Priority queues
An abstract data structure where each element has an associated priority. The element with the highest priority in the queue is served first.
Applications
Priority queues have a variety of important applications: Dijkstra’s shortest path algorithm
Prim’s algorithm (minimum weight spanning trees) Process sheduling
(FIT3155 S1 2022, Monash University) Binomial heaps 5 / 36

Priority queues (implemented using heaps)
Recall from FIT2004 that the heap data structure was used to implement priority queues in several applications:
Dijkstra’s shortest path algorithm Prim’s algorithm
Recall also that this data structure supports the following operations*:
insert a new element (containing key w/ payload) into a heap identify the min element in an existing heap
extract-min (identify and delete min) element in an existing heap decrease-key of an element in an existing heap
*As with these slides, default heap operations in the rest of the slides are defined
over a min-heap. One could alternatively define max, extract-max, increase-key operations on a max-heap.
(FIT3155 S1 2022, Monash University) Binomial heaps 6 / 36

Binary heaps (recap) Properties
Structure: A binary heap is a complete binary tree, i.e. every level is full except possibly the last.
Order (min-heap): Every node is less than or equal to its children.
1 2 3 4 5 6 7 8 9 10
(FIT3155 S1 2022, Monash University) Binomial heaps 7 / 36

Binary heaps (recap)
Binary heap
extract-min
decrease-key
O(logN) worst-case O(1) amortized
(FIT3155 S1 2022, Monash University) Binomial heaps 7 / 36

Mergeable heaps
Today (binomial heaps) and next week (Fibonacci heaps), we will learn about mergeable heaps that support (at least) the following operations􏰤:
insert: inserts a new element into the existing heap
min: finds the min element in the heap
extract-min: finds and deletes the min element in the heap merge: merges two heaps into one
decrease-key: decreases the elements key delete: removes an element from the heap
Note, merging two binary heaps requires O(n)-time.
􏰤Again, the slides define these default heap operations over a min-heap. One could alternatively define max, extract-max, increase-key operations on a max-heap.
(FIT3155 S1 2022, Monash University) Binomial heaps 8 / 36

Before Binomial heap, let us define a binomial tree Binomial trees are defined
recursively:
The binomial tree of order 0 (or
B0 in short) is a single node tree
The binomial tree of order 1 (B1) is created from two B0 trees, by making one B0 tree the child of the other.
The binomial tree of order 2 (B2) is created from two B1 trees, by making one B1 tree the child of the other.
and so on…
(FIT3155 S1 2022, Monash University)
Binomial heaps

Properties of a Binomial tree
Any binomial tree of order k has the following properties:
The number of nodes in any Bk is 2k.
The height of any Bk is k.
The root node of any Bk tree has k subtrees as children.
Deleting the root node of Bk (with its edges/links) yields k independent lower order binomial trees Bk−1, Bk−2, . . . , B0.
Example: Binomial tree, B5:
(FIT3155 S1 2022, Monash University) Binomial heaps 10 / 36

Why are these trees called binomial? Example: Binomial tree, B5
Main property
A main property of any Bk tree is that the number of nodes at any given depth d is given by the binomial coefficient 􏰨k􏰩, that is “k-choose-d”
(FIT3155 S1 2022, Monash University) Binomial heaps 11 / 36

Why are these trees called binomial? Example: Binomial tree, B5
(FIT3155 S1 2022, Monash University)
Binomial heaps 11 / 36

What is a binomial heap?
A binomial heap is a forest (i.e., a set) of binomial trees such that:
each binomial tree in the set satisfies the heap property – i.e., each tree-node’s key is ≤ its children’s keys.
There is at most one (i.e. either 0 or 1) binomial tree of any given order in that set.
On the right is a binomial heap that contains a collection/set of binomial trees:
one B4 tree zero B3 trees zero B2 trees one B1 tree one B0 tree
(FIT3155 S1 2022, Monash University)
Binomial heaps 12 / 36

How to find which order trees are there in a Binomial heap?
For the above binomial heap: N = 19.
(Minimal) Binary representation of 19 gives: 1 0 0 1 1
The ‘1’s above are at bit positions 0,1 and 4
Therefore, the binomial heap with N = 19 contains 3 binomial trees: B0,B1,B4 trees.
(FIT3155 S1 2022, Monash University) Binomial heaps 13 / 36

Binomial heap properties
Properties
For any binomial heap containing N elements, the following properties hold:
The ‘1’s in the minimal binary representation of N tell us which order/degree binomial trees form the binomial heap of N elements.
There are at most ⌊log2 N ⌋ + 1 binomial trees The height of each binomial tree is ≤ ⌊log2 N⌋
the element with minimum key in the entire heap will be one of the root nodes of the trees in the collection.
(FIT3155 S1 2022, Monash University) Binomial heaps 14 / 36

Representing a binomial heap
Unlike binary heaps, binomial heaps are stored explicitly using a tree data structure. Each node x:
􏰥 is denoted by a x.key (one may also include additional information as x.payload).
􏰥 has a pointer x.parent to its parent node
􏰥 has a pointer x.child to its leftmost child node
⋆ If node x has zero children, then x.child = nil
􏰥 has a pointer x.sibling to the immediate sibling of x to its right.
⋆ If node x is the rightmost child of its parent, then x.sibling = nil
􏰥 stores x.degree which is the number of children of x (i.e., same as the order of the binomial tree rooted at x)
Finally, the roots of the binomial trees within a binomial heap are organized in a linked list, referred to as the root list.
(FIT3155 S1 2022, Monash University) Binomial heaps 15 / 36

Binomial heap data structure representation – example
􏰤Image from CLRS: Introduction to Algorithms
(FIT3155 S1 2022, Monash University) Binomial heaps 16 / 36

operations on a binomial heap
(FIT3155 S1 2022, Monash University) Binomial heaps 17 / 36

Merging two binomial trees into one
Before merging two binomial heaps, we will first see a more atomic operation that becomes necessary, i.e., merging two binomial trees.
Merging two binomial trees, each of the same order (say) k results in an order k + 1 binomial tree, where:
􏰥 the two roots are linked, such that…
􏰥 …the root containing the larger key becomes the child of the root
with smaller key.
(FIT3155 S1 2022, Monash University) Binomial heaps 18 / 36

Merging two binomial trees into one (implementation) First make the tree with the smaller root (r1) the parent of
the tree with the larger root (r2).
Make the right sibling of r2 the left child of r1. Make r2 the left child of r1.
Increment the degree of r1.
(FIT3155 S1 2022, Monash University) Binomial heaps 19 / 36

Merging two binomial trees into one (implementation) First make the tree with the smaller root (r1) the parent of
the tree with the larger root (r2).
Make the right sibling of r2 the left child of r1. Make r2 the left child of r1.
Increment the degree of r1.
All of the above takes O(1)-time.
(FIT3155 S1 2022, Monash University) Binomial heaps 19 / 36

Binomial heap operation – merge two binomial heaps into one
With merging of two binomial trees established (see previous slide), we can now define merging of two binomial heaps (each containing a collection of trees).
Heaps are merged in a way that is reminiscent of how we add two numbers in binary:
Example: addition of 19 + 7 = 26 in binary
Order: 4 3 2 1 0 carry: 1 1 1
10011 +00111 Result: 1 1 0 1 0
(FIT3155 S1 2022, Monash University)
Binomial heaps 20 / 36

Example of merging 2 binomial heaps containing 19 and 7 elements each
(To be discussed during the lecture)
(FIT3155 S1 2022, Monash University) Binomial heaps 21 / 36

Implementing merge(H1,H2) – first phase
Merging any two binomial heaps can be implemented in 2 phases:
First phase
Combine the root level linked-lists (root lists) of H1 and H2, such that the degrees are monotonically increasing. Note: This potentially violates the binomial heap property that requires at most one binomial tree of any given degree – see slide #12.
(FIT3155 S1 2022, Monash University) Binomial heaps 22 / 36

Implementing merge(H1,H2) – second phase Second phase
Scan the combined root list (from first phase) and iteratively check the degrees of successive root nodes to consolidate them by merging trees (with same degrees) in order to get back a valid binomial heap (with at most one tree of any degree).
(FIT3155 S1 2022, Monash University) Binomial heaps 23 / 36

Complexity of merge(H1, H2)
Let H1 contain n1 elements, and H2 contain n2 elements, and N = n1 + n2
Running time is O(logN) worst-case:
􏰥 First phase results in a root list with at most ⌊log n1⌋ + ⌊log n2⌋ + 2
􏰥 In second phase, each iteration takes O(1) time, with at most
⌊log n1⌋ + ⌊log n2⌋ + 2 iterations.
􏰥 Since: ⌊logn1⌋+⌊logn2⌋+2≤2⌊logN⌋+2
􏰥 Thus, merging two heaps, in worst case, requires O(logN) effort.
(FIT3155 S1 2022, Monash University) Binomial heaps 24 / 36

Binomial heap operation – extract-min
We use this to identify and delete the minimum element among all root
nodes of the trees in the heap.
Identify the min node among the nodes in the root level of the heap,
and delete it.
From slide #10, we know that deleting the root node of any Bk tree yields: Bk−1,Bk−2,…,B0.
Promote these subtrees to the root level of the existing binomial heap. The result is similar to the result after first phase of merge operation…
…with potentially multiple trees of the same degree (violating binomial heap def’n – see slide #12).
Now consolidate this current state of the tree so that at most one binomial tree of any degree will be present. This is same as the second phase of merge.
(FIT3155 S1 2022, Monash University) Binomial heaps 25 / 36

Binomial heap operation – extract-min
We use this to identify and delete the minimum element among all root
nodes of the trees in the heap.
Identify the min node among the nodes in the root level of the heap,
and delete it.
From slide #10, we know that deleting the root node of any Bk tree
yields: Bk−1,Bk−2,…,B0.
Promote these subtrees to the root level of the existing binomial heap.
The result is similar to the result after first phase of merge operation… …with potentially multiple trees of the same degree (violating
binomial heap def’n – see slide #12).
Now consolidate this current state of the tree so that at most one binomial tree of any degree will be present. This is same as the second phase of merge.
(FIT3155 S1 2022, Monash University) Binomial heaps 25 / 36

Binomial heap operation – extract-min
We use this to identify and delete the minimum element among all root
nodes of the trees in the heap.
Identify the min node among the nodes in the root level of the heap,
and delete it.
From slide #10, we know that deleting the root node of any Bk tree
yields: Bk−1,Bk−2,…,B0.
Promote these subtrees to the root level of the existing binomial heap.
The result is similar to the result after first phase of merge operation…
…with potentially multiple trees of the same degree (violating binomial heap def’n – see slide #12).
Now consolidate this current state of the tree so that at most one binomial tree of any degree will be present. This is same as the second phase of merge.
(FIT3155 S1 2022, Monash University) Binomial heaps 25 / 36

Binomial heap operation – extract-min
We use this to identify and delete the minimum element among all root

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts