CSC263 – Week 2, Lecture 2
Cristyn Howard
Wednesday, January 17, 2018
ADT Data Structure Operations Mergeable Priority Queues Binomial Heap insert, min, extract-min, merge
MERGE:
• Merging two binary forests is directly analogous to adding two binary numbers.
• Any time both of the forests being added each have an Sk tree of the same size, they merge to form a new Sk+1 tree.
• This is the equivalent of adding two 1’s in the same digit of two binary numbers, and carrying the 1 to the next column.
11
11 |T| + 111 |Q|
• Every time a tree is ”carried” to the next column, it indic
+
= S3
S2 S1 S0 Q
S1 T+Q = 1 0 1 0 |T+Q|
S2 S1
S1 S0 T
1