CSC263 – Week 2, Lecture 1
Cristyn Howard Monday, January 15, 2018
ADT
Priority Queues Mergeable Priority Queues
Data Structure Heaps Binomial Queues
INSERT yes O(log n)
MIN yes O(log n)
EXTRACTMIN yes
O(log n)
MERGE NO O(log n)
If a CPU has two cores, each with a Priority Queue of tasks to perform, it might need to merge them. This is not easy to accomplish with Heaps, however it is possible with…
Binomial Heaps Sktree: S0=⃝
Sk = take two Sk−1 trees, make the roof of one the parent of the root of the other. S0 S1 S2 S3 S4
⃝
⃝ ⃝
⃝ ⃝⃝
⃝
⃝
⃝⃝⃝ ⃝⃝⃝
⃝
⃝
⃝⃝⃝⃝
⃝⃝⃝ ⃝⃝⃝
⃝
⃝⃝⃝ ⃝
• Each Sk tree is attached to {S0, S1, …, Sk−1}, has 2k total nodes, and k nodes at depth d. d
A binomial forest of size m, denoted Fm, is a sequence of Sk trees with increasing k, and a total of m nodes in the entire forest.
• Represent the number m in binary, each 1 digit in the resulting number represents an Sk tree in the forest. Ex: m=7=<1,1,1>2=22 +21 +20 ∴ Fm ={S2,S1,S0}
• α(m) = number of 1’s in the binary representation of m.
• Fm has α(m) trees, and m − α(m) edges.
• Note: a ’forest’ is just the structure, it becomes a heap when keys are added.
Min heap has property that the key of the parent is SMALLER than the key of the children.
1
Some examples of binary forests with keys that conform to the min heap property:
m = 7 =< 1, 1, 1 >2
Fm ={S2,S1,S0}
S = {10,13,1,3,8,18,7}
m = 0 =< 1, 0, 0, 1 >2
Fm ={S3,S0}
S = {6,1,7,3,4,5,2,2,21}
3 1 7 8 13
18
1
3 2 765
21
10
2 4
These forests must have pointers to allow for navigation between trees and interaction with the data struc- ture. These pointers are NOT edges in the trees.
Each node stores pointers to: parent, left child, right sibling.
2