Exploring Advanced Data Structures: Heaps, Binomial Trees, and Tournaments

Heaps Binomial Heaps Lazy Binomial Heaps 1

Heaps / Priority queues Binary Heaps Binomial Heaps Lazy Binomial Heaps O(1) O(1) O(logn) O(logn) O(1) Fibonacci Heaps Insert Find-min Delete-min Decrease-key Meld O(logn) O(1) O(logn) O(logn) O(logn) O(1) O(logn) O(logn) O(logn) O(1) O(1) O(logn) O(1) O(1) Worst case Amortized Delete can be implemented using Decrease-key + Delete-min Decrease-key in O(1) time important for Dijkstra and Prim

Binomial Heaps 3

Binomial Trees B0 B1 B2 B3 B4 4

Binomial Trees B0 B1 B2 B3 B4 5

Binomial Trees B0 B1 B2 B3 Bk Bk Bk 1 Bk 2 Bk 1 Bk 1 6

Binomial Trees Bk Bk B0 Bk 1 Bk 1 Bk 2 Bk 1 7

Min-heap Ordered Binomial Trees 2 15 17 25 5 40 20 35 18 11 38 45 58 31 45 67 key of child key of parent 8

Tournaments Binomial Trees D D D F F A C G E B A D F G A B C D E F G H H The children of x are the items that lost matches withx, in the order in which the matches tookplace. 9

Binomial Heap A list of binomial trees, at most one of eachrank Pointer to root with minimalkey 23 9 15 33 40 20 35 Each number n can be written in a unique way as a sum of powers of 2 45 58 31 11 = (1011)2 = 8+2+1 At most 67 log2(n+1) trees

Ordered forest Binary tree 23 9 15 x 33 40 20 35 info key child next 45 58 31 67 child leftmost child next next sibling 2 pointers per node 11

Forest Binary tree 23 15 23 9 9 33 40 20 35 33 15 45 58 31 40 67 45 20 Heap order half ordered 67 58 31 35

Binomial heap representation Q 2 pointers pernode No explicit rank information How do we determine ranks? n first min x 23 9 15 33 40 20 35 info key child next 31 45 58 StructureV 67

Alternative representation Q Reverse siblingpointers Make lists circular Avoids reversals during meld n first min 23 9 15 33 40 20 35 info key child next 31 45 58 StructureR [Brown(1978)] 67

Linking binomial trees a b x Bk a y b Bk 1 Bk 1 O(1) time 15

Linking binomial trees Linking infirst representation Linking insecond representation 16

Melding binomial heaps Link trees of same degree Q1: Q2:

Melding binomial heaps Link trees of same degree B1 B1 B2 B2 B3 B3 B3 Q1: Q2: B0 B0 B3 B4 Like adding binary numbers Maintain a pointer to the minimum O(logn) time 18

Insert 23 15 9 11 33 40 20 35 45 58 31 67 New item is a one tree binomial heap Meld it to the originalheap 19 O(logn) time

Delete-min 23 15 9 33 40 20 35 When we delete the minimum, we get a binomial heap 45 58 31 67 20

Delete-min 23 15 33 40 20 35 When we delete the minimum, we get a binomial heap 45 58 31 Meld it to the originalheap 67 O(logn) time (Need to reverse list of roots in first representation) 21

Decrease-key using sift-up 2 I 15 5 17 25 40 20 35 18 11 38 45 45 58 31 Decrease-key(Q,I,7) 67 22

Decrease-key using sift-up 2 I 15 17 25 5 40 20 35 18 11 38 7 45 58 45 Need parent pointers (not needed before) 67 23

Decrease-key using sift-up 2 I 15 17 25 5 7 35 40 18 11 38 45 58 20 45 67 Need to update the node pointed byI 24

Decrease-key using sift-up 2 I 15 17 25 5 7 35 40 18 11 38 45 58 20 45 67 Need to update the node pointed byI 25

Decrease-key using sift-up 2 I 7 5 17 25 40 15 35 18 11 38 45 45 58 20 How can we do it? 67

Q Adding parent pointers n first min 23 9 15 33 20 35 40 45 58 31 67 27

Q Adding a level of indirection n Endogenous vs. exogenous first min 23 9 15 x I 33 20 35 40 item child next parent 45 58 31 info key node Nodes and items are distinct entities 67 28

Heaps / Priority queues Binary Heaps Binomial Heaps Lazy Binomial Heaps O(1) O(1) O(logn) O(logn) O(1) Fibonacci Heaps Insert Find-min Delete-min Decrease-key Meld O(logn) O(1) O(logn) O(logn) O(logn) O(1) O(logn) O(logn) O(logn) O(1) O(1) O(logn) O(1) O(1) Amortized Worst case

Lazy Binomial Heaps 30

Binomial Heaps A list of binomialtrees, at most one of each rank, sorted by rank (at most O(logn) trees) Pointer to root with minimal key Lazy Binomial Heaps An arbitrary list of binomial trees (possibly n trees of size 1) Pointer to root with minimal key

Lazy Binomial Heaps An arbitrary list of binomial trees Pointer to root with minimal key 15 19 10 29 9 59 87 20 40 20 35 33 45 58 31 67 32

Lazy Meld Concatenate the two lists of trees Update the pointer to root with minimal key O(1) worst case time Lazy Insert Add the new item to the list of roots Update the pointer to root with minimal key O(1) worst case time 33

Lazy Delete-min ? Remove the minimum root and meld ? 10 29 15 9 19 59 33 40 20 35 20 45 58 31 67 May need (n) time to find the new minimum

Consolidating / Successive Linking 10 29 15 59 40 20 35 19 33 45 58 31 20 67 3 0 1 2

Consolidating / Successive Linking 29 15 59 40 20 35 19 33 45 58 31 20 67 10 3 0 1 2

Consolidating / Successive Linking 15 59 40 20 35 19 33 45 58 31 20 67 10 29 3 0 1 2

Consolidating / Successive Linking 59 40 20 35 19 45 58 31 20 67 10 15 29 33 3 0 1 2

Consolidating / Successive Linking 40 20 35 19 45 58 31 20 67 10 15 29 59 33 3 0 1 2

Consolidating / Successive Linking 20 35 19 31 20 10 40 15 29 45 58 33 59 67 3 0 1 2

Consolidating / Successive Linking 35 19 20 10 40 15 29 20 45 58 33 59 67 31 3 0 1 2

Consolidating / Successive Linking 19 20 35 10 59 40 15 29 20 45 58 33 67 31 3 0 1 2

Consolidating / Successive Linking 19 20 10 20 40 15 29 35 31 45 58 33 67 59 3 0 1 2

Consolidating / Successive Linking At the end of the process, we obtain a non-lazy binomial heap containing at most log(n+1) trees, at most one of each rank 10 20 40 15 29 35 31 45 58 33 19 67 20 59 3 0 1 2

Outline Lazy Union Extract-Min Analysis

Amortized Thinking Union violates binomial heaps structural property Let the Extract-Min convert the lazy version back to a clean binomial heap Extract-Min can cost ( n ) in worst-case However, it is O( log n ) amortized time ! Union : increase potential Extract-Min : decrease potential

Extract-Min : Amortized Analysis Let Ti be the number of trees after the ith operation Let r be the rank of the tree containing the min. Extract-Min actual cost ( # trees ) = ( r + Ti-1 ) = O( log n + Ti-1) r = O( log n ) since all the trees are binomial trees

Extract-Min : Amortized Analysis Let the potential function i = Ti ai = ci + i - i-1 = O( log n + Ti-1) + (Ti - Ti-1) = O( log n + Ti-1) + O( log n ) - Ti-1 = O( log n ) + O( Ti-1) - Ti-1 = O( log n )

Potential Energy H

Potential Energy H Lazy Binomial Heap - Insert