Skew Heaps Advanced)

Skew Heaps Rabea Aden

NUCES-FAST • Advanced Data Structures • Spring 2007

Leftist Tree • Invented by Daniel Sleator and Robert Trajan • A self-adjusting heap similar to Leftist Heaps • No structural constraint • Amortized time complexity of O(log n)

NUCES-FAST • Advanced Data Structures • Spring 2007

Heap-order Property • Min Leftist Heap ∀ X ∈ Heap key(X) ≥ key(Parent(X))

• Max Leftist Heap ∀ X ∈ Heap key(X) ≤ key(Parent(X))

If X is root Parent (X) = root NUCES-FAST • Advanced Data Structures • Spring 2007

Structure of a Node

Left Right Data Pointer Pointer

No balance information is stored in the node

NUCES-FAST • Advanced Data Structures • Spring 2007

Operations • • • • •

BuildHeap FindMin Merge Insert DeleteMin

O(N) O(1) O(log N) O(log N) O(log N)

NUCES-FAST • Advanced Data Structures • Spring 2007

Weight • denoted by w(X) • Number of internal nodes in subtree with root X

w(X) = 1 + w(leftChild(X)) + w(rightChild(X))

NUCES-FAST • Advanced Data Structures • Spring 2007

Heavy and Light Nodes • X — a nonroot node • X is heavy if w(X) ≤ w(Parent(X)) / 2

• X is light if w(X) > w(Parent(X)) / 2

NUCES-FAST • Advanced Data Structures • Spring 2007

Potential Function

NUCES-FAST • Advanced Data Structures • Spring 2007

General Idea • All insertions and merges are performed on the rightmost path containing at most  log2 (n + 1) nodes

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge • O(log N) time • It is a fundamental operation – Both Insert and DeleteMin are based on Merge – Insert: • The key to be inserted is a one-node heap • Merge this one-node heap with the given min leftist heap

– DeleteMin • Delete root, left and right child of root are two min leftist heaps • Merge the two min leftist heaps NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Algorithm (Recursive) Merge(H1, H2) If both heaps are Leftist If one heap is NULL then return the other If data(H1) > data(H1) then swap H1 and H2 If rightChild(H1) is NULL then rightChild(H1) = H2 Otherwise, Recursively Merge rightChild(H1) and H2 If H1 ≠ last node on Rightmost Path then swap children of H1

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H1

H2

1

2

5 6

8 12

16

4

36

14

7 10

40

18 28

Both H1 and H2 are Min Leftist Heaps

NUCES-FAST • Advanced Data Structures • Spring 2007

22 25

Merge H1 & H2 H1

H2

1

Both H1 and H2 are not NULL

5 6

8 12

2

4

16

36 40

14

7 10

18 28

22 25

Merge (H1, H2) Compare root(H1) '1' & root(H2) '2' — H1 has smaller root NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H1

H2

1 5 6

2

H1

8 12

16

4 36

14

40

7 10

18 28

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

22 25

Merge H1 & H2 H2

1

Both H1 and H2 are not NULL 4 4

8

5 6

12

2

H1

16

36 40

14 14

7 7 10 10

18 18 28 28

22 22 25 25

Merge (H1, H2) Compare root(H1) '8' & root(H2) '2' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '2' & root(H2) = '8' • Spring 2007

Merge H1 & H2 H2

1 5 6

8

H1

16

2 12 4 14

40

7 10

18 29 28

36

22 26 25

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H2

1

Both H1 and H2 are not NULL

5 6

2

H1

12 4 14

7 10

18 28

8 16

36 40

22 25

Merge (H1, H2) Compare root(H1) '7' & root(H2) '8' — H1 has smaller root NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H2

1

8

5 6

2

H1

12 4 14

18 28

36 40

7 10

16

22 25

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H2

1

Both H1 and H2 are not NULL

5 6

16

2 12 4 14

7 10

8

18 2828

H1

0 091H2 17 37410

36 40

22 8 1625

36 40

Merge (H1, H2) Compare root(H1) '22' & root(H2) '8' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '8' & root(H2) = '23' • Spring 2007

Merge H1 & H2 H2

1

22

5 6

25

2 12 4 14

7 10

18 28

H1

8 16

36 40

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

0 091H2 17 37410

Merge H1 & H2 H2

1

Both H1 and H2 are not NULL

5 6

0 091H2 17 37410

25

2 12 4 14

22

7 10

18 28

8 16

H1

36 40

Merge (H1, H2) Compare root(H1) '36' & root(H2) '22' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '22' & root(H2) = '36' • Spring 2007

Merge H1 & H2 H2

1

36

5 6

40

2 12 4 14

7 10

18 28

8 16

H1

22 25

NULL

Since, rightChild(H1) is NULL rightChild(H1) = H2 NUCES-FAST • Advanced Data Structures • Spring 2007

0 091H2 17 37410

Merge H1 & H2 H2

H1 is NULL

1 5 6

36 40

2 12 4 14

7 10

18 28

8 16

22 25

H1

NULL

Merge (H1, H2) Since root(H1) is 'NULL' swap(H1, H2) NUCES-FAST Advanced Data Structures • Spring 2007 Now, root(H1) =• '36' & root(H2) = 'NULL'

Merge H1 & H2 H2

H2 is NULL

1

NULL

5 6

2 12 4 14

7 10

18 28

Swap children of each node on the Rightmost Path except the last node

8 16

22

H1

25 36 40

NULL

rightChild(H1) is NULL NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 swap( leftChild(H1), rightChild(H1) ) 1 5 6

2 12 4 14

7 10

18 28

H1 moves up to '22' 8

16

22 25 36 36 25 40 40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

H1

Merge H1 & H2 swap( leftChild(H1), rightChild(H1) ) 1 5 6

2 12 4 14

7 10

18 28

H1 moves up to '8' H1

8 16 16

22 22 25 36 25 40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 swap( leftChild(H1), rightChild(H1) ) 1 5 6

2 12 4 14

H1

7 10

18 18 28 28

8 22

16 16

36 25 40

NUCES-FAST • Advanced Data Structures • Spring 2007

H1 moves up to '7'

Merge H1 & H2 swap( leftChild(H1), rightChild(H1) ) 1 5 12 7 4

6

814 14 22 36 25 40

H1

2 4 7 1018 814

16 28 22

H1 moves up to '2' 1018

16 28

36 25 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H1

swap( leftChild(H1), rightChild(H1) )

11

H1

52 7

6

36 25 40

12 74 18 8 14

8 22

25

16 28 22

6

12 4

1018

14

H1 moves up to '1' 10

16 28

36 25 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge H1 & H2 H1

Root

1 2

5

7 8 22

4 18

14

6 10

12

H1 is returned Root pointer now points to H1

16 28

36 25 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Algorithm (Iterative) Merge(H1, H2) 

Pass 1 — Down the Heap Sort nodes on rightmost paths of H1 and H2 in ascending order (leftChild of each node remains) A new tree H is created by merging the sorted nodes



Pass 2 — Up the Heap ∀ nodes X Є rightmost path of H from leaf to the root If X ≠ last node on rightmost path then then swap children of X

NUCES-FAST • Advanced Data Structures • Spring 2007

Time Complexity of Merge • O(log n) • As only shortest path is traversed

NUCES-FAST • Advanced Data Structures • Spring 2007

Insert • O(log N) time Insert is based on Merge  Existing min leftist heap — H1  The key to be inserted is a one-node heap — H2  Merge this one-node heap H1 with the given min leftist heap H2

NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 H1

H2

1

2

5 6

8 12

16

36 40

H1 — existing Heap H2 — one-node heap containing node to be inserted Both H1 and H2 are Min Leftist Heaps NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 H1 H1

H2

1

Both H1 and H2 are not NULL

5 6

0

3 2

8 12

16

36 0

40

Merge (H1, H2) Compare root(H1) '1' & root(H2) '2' — H1 has smaller root NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 H1

H2

1

H1

5 6

2

8 12

16

36 40

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 H2

1

Both H1 and H2 are not NULL H1

8

5 6

2

12

16

36 40

Merge (H1, H2) Compare root(H1) '8' & root(H2) '2' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '2' & root(H2) = '8' • Spring 2007

Insert 2 H2

1 5 6

8

H1

16

22 12

8 NULL 16

36 40

36 40

Since, rightChild(H1) == NULL rightChild(H1) = H2 NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 H2

H2 is NULL

11 55 66

H1

22 12 12

NULL H1

88 16 16

H1

36 36

Swap children of each node H1 on the Rightmost Path except the last node

40 40 NULL

rightChild(H1) is NULL Since, rightChild(H1) ≠ NULL H1 now points to its rightChild '8' '36' NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 swap( leftChild(H1), rightChild(H1) ) 1 5 6

22 12

8 16 36 16 40

H1 H1

36 16 36 40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

moves up to '8'

Insert 2 swap( leftChild(H1), rightChild(H1) ) 11 55 66

22 12 12

8 NULL 36

40

36 16 36

H1

88

H1 moves up to '2' 16 16

40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 2 swap( leftChild(H1), rightChild(H1) ) 1

H1

5 2 8 6 36 40

5 2 12 12

16

6 8 36

12 NULL 16

40

NUCES-FAST • Advanced Data Structures • Spring 2007

H1 moves up to '1'

Insert 2 H1

Root

1 2 8 36

5 6

16

12

H1 is returned Root pointer now points to H1

40

NUCES-FAST • Advanced Data Structures • Spring 2007

Time Complexity of Insert • O(log n) • Create a one-node heap — O(1) • Merge — O(log n) – As only shortest path is traversed

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin • O(log N) time DeleteMin is based on Merge  Delete root — (minimum value is in root)  Left and right children of root are two min leftist heaps — H1 and H2 respectively  Merge the two min leftist heaps H1 and H2

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Root 2

2 1 1

1

6 5

9 8

0

0

0

0

7 6

13 12

17 16

37 36 0

41 40

Delete Minimum Key '2'

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot Root

11

H1

H2

5 6

8 12

16

36 40

Save old value of root H1 = root→leftChild H2 = root→rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1

H1

Both H1 and H2 are not NULL

6 5 7 6

H2

13 12

16

8 36 40 41

Merge (H1, H2) Compare root(H1) '5' & root(H2) '8' — H1 has smaller root NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1

H1

5 6

H2

8

H1

12

16

36 40

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1

Both H1 and H2 are not NULL

5 6

H2

H1

12

16

8 36 40

Merge (H1, H2) Compare root(H1) '8' & root(H2) '2' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '2' & root(H2) = '8' • Spring 2007

DeleteMin oldRoot

1

5 6

H1

H2

12

8 16

36 40

Since, rightChild(H1) ≠ NULL H1 now points to its rightChild NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1

Both H1 and H2 are not NULL

5 6

8

H2

12

H1

0

17

36 40

Merge (H1, H2) Compare root(H1) '36' & root(H2) '12' — H2 has smaller root swap(H1, H2) NUCES-FAST Advanced Data Structures Now, root(H1) =• '36' & root(H2) = '12' • Spring 2007

DeleteMin oldRoot

1

36

5 6

8 16

H2

H1

40

12 36

rightChild(H1) is NULL 40

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1 5 6

36 NULL 8

16

H2

H1

40

12 36 NULL 40

Since, rightChild(H1) == NULL rightChild(H1) = H2 NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

H2 is NULL

1

H2

5 6

NULL 8

16

H1

12 36

Swap children of each node on the Rightmost Path except the last node

rightChild(H1) is NULL 40 NULL Since, rightChild(H1) ≠ NULL H1 now points to its rightChild '36' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

swap( leftChild(H1), rightChild(H1) ) 1

5 6

88 16 16

36 NULL 40

H1 moves up to '12' 12

H1

36 NULL 40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

swap( leftChild(H1), rightChild(H1) ) 1

5 6

88 16 12 16

36 40

H1

12 16 12 36 36

NULL

40 40

NUCES-FAST • Advanced Data Structures • Spring 2007

H1 moves up to '8'

DeleteMin oldRoot

swap( leftChild(H1), rightChild(H1) ) 1

55 6 8 12 36 40

H1

6 88 16 12

H1 moves up to '5' 16 16

36 40

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin oldRoot

1

Root

H1

Delete old Root

5 8 12

6 16

H1 is returned Root pointer now points to H1

36 40

NUCES-FAST • Advanced Data Structures • Spring 2007

Time Complexity of DeleteMin • O(log n) • • • •

Delete root — O(1) Initialize H1 with left child of root — O(1) Initialize H2 with right child of root — O(1) Merge — O(log n) – As only shortest path is traversed

NUCES-FAST • Advanced Data Structures • Spring 2007

Leftist Heaps vs Skew Heaps • More space • Explicit structural constraints guarantees efficiency

• Less space • No structural constraint guarantees efficiency • Easier to implement

NUCES-FAST • Advanced Data Structures • Spring 2007