Weight-biased Leftist Heaps Advanced)

Weight-biased Leftist Heaps Rabea Aden

NUCES-FAST • Advanced Data Structures • Spring 2007

Weight-biased Leftist Tree • Invented by Seonghun Cho and Sartaj Sahni • A Weight-biased Leftist Tree is a priority queue • An alternative to Height-biased Leftist Trees • It satisfies the leftist structural property For any node X Є Weight-biased Leftist Tree, Rightmost path is the Shortest

NUCES-FAST • Advanced Data Structures • Spring 2007

Weight • denoted by w(X) • Number of internal nodes in subtree with root X w(NULL) = 0 w(X) = 1 + w(leftChild(X)) + w(rightChild(X))

NUCES-FAST • Advanced Data Structures • Spring 2007

Weight 8

4

3

2

1

2

0 Null

1

0

0

0

Null Null Null 0 0 Null Null

0 Null

1

0 Null

w(NULL) = 0

0 Null

w(X) = 1 + w( leftChild(X) ), w( rightChild(X) ) NUCES-FAST • Advanced Data Structures • Spring 2007

Structural Property •

Weight-biased Leftist Property ∀ X ∈ WBLT

• • • •

w(LeftChild(X)) ≥ w(RightChild(X))

Tree is unbalanced Biased towards left Left paths are long, giving the name Leftist Heap Rightmost path is the shortest NUCES-FAST • Advanced Data Structures • Spring 2007

Structural Property T1

T2

8

9

4 2 1

3 1

1

4 1

2 1

4* 1

1

Leftist Heap Property Violated w(Left Child) < w(Right Child)

2 1

Weights: T1 is a Weight-biased Leftist Tree, T2 is not

NUCES-FAST • Advanced Data Structures • Spring 2007

Weight-biased Leftist Heap • A Heap-ordered Weight-biased Leftist Tree

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

Binary Heap vs. Weight-biased Leftist Heap Binary Heap

Weight-biased Leftist Heap

— Perfectly balanced

— Very unbalanced

Operations

Binary Heap

Weight-biased Leftist Heap

BuildHeap FindMin Merge Insert DeleteMin

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

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

NUCES-FAST • Advanced Data Structures • Spring 2007

Binary Heap vs. Weight-biased Leftist Heap Binary Heap

Weight-biased Leftist Heap

— Perfectly balanced

— Very unbalanced

Operations

Binary Heap

Weight-biased Leftist Heap

BuildHeap FindMin Merge Insert DeleteMin

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

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

Merge is expensive in ordinary Heaps NUCES-FAST • Advanced Data Structures • Spring 2007

Theorem In a weight-biased leftist tree, the number of nodes N on the rightmost path of any node x is ≤ log2 (w(x) + 1) Proof is by Induction

NUCES-FAST • Advanced Data Structures • Spring 2007

Structure of a Node

Left Lsize Pointer

Data

Right Rsize Pointer

Apart from data, left and right pointers, each node also contains Lsize and Rsize — the number of nodes in left and right subtrees, respectively NUCES-FAST • Advanced Data Structures • Spring 2007

Design • A Weight-biased Leftist Tree is a priority queue • A header node points to the root of the weightbiased leftist tree with data = -∞ and left pointer pointing to itself • A bottom node acts as a common NULL node with data = ∞

NUCES-FAST • Advanced Data Structures • Spring 2007

Structure of Header & Bottom Nodes

Header Node

+∞ -∞ 0 Bottom Node

∞

Figure Empty min WBLT NUCES-FAST • Advanced Data Structures • Spring 2007

Structure of Header & Bottom Nodes Header Node

+∞ -∞ 4 4 2 3 1 2 1 7 0

1 0 5 0

1 0 9 0

Bottom Node

∞

Figure min WBLT 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

General Idea • All insertions and merges are performed on the rightmost path containing at most  log2 (n + 1) nodes • This may violate Weight-biased Leftist Heap Property • Weight-biased Leftist Heap Property can be easily restored

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 node • Merge this node 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

Insert Existing min leftist heap — H1 The key to be inserted is a node — Y, where data(Y) = key X = header node While data( rightChild(X) ) < key Increment Rsize(X) by 1 If Lsize(X) < Rsize(X) then swap children of X and X = leftChild(X) Otherwise X = rightChild(X)

leftChild(Y) = rightChild(X) and rightChild(Y) = bottom node Lsize(Y) = Rsize(X) and Rsize(Y) = 0 If Lsize(X) = Rsize(x) then  rightChild(X) = leftChild(X)  leftChild(X) = Y  Increment Lsize(X) by 1

Otherwise  rightChild(X) = Y  Inrement Rsize(X) by 1

NUCES-FAST • Advanced Data Structures • Spring 2007

Insert 3 ∞ -∞ 99 ∞ -∞ -∞ 8

Header HeaderNode Node Header Node Node Header

X = header node Since data(rightChild(X)) '5' > key '3' leftChild('3') = rightChild(X) '5' rightChild(Y) = bottom node 2

1 0 29 0 1

99

8

88 33 00 4 5 3 8

4

4 5 3

2 11 1 4

Lsize('3') = Rsize(X) 1 20 02 2 '8' 1 Rsize('3') = 0 0 29 01 20 0

0 3 0

1

11 1 0 23 0 1 0 23 0

1

3

1 13 1 3

1

1 13 1 0 19 0 0 17 0 1 1 0 19 0

0 17 0

1 0 29 0

Since Lsize(X) ≠ Rsize(X) rightChild(X) = '3' Increment Rsize(X) by 1 '9'

BottomNode Node Bottom

∞

Bottom Node

∞

NUCES-FAST • Advanced Data Structures • Spring 2007

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

NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Algorithm Merge(H1, H2) If both heaps are Leftist If one heap is NULL then return the other while H1 ≠ NULL If Lsize(H1) < Rsize(H1) + w(H2) then work on leftChild(H1) rightChild(H1) = leftChild(H1), Rsize(H1) = Lsize(H1), Lsize(H1) = Rsize(H1) + w(H2) If data(H1) > data(H2) then leftChild(H1) = H2, H1 moves to its leftChild and H2 moves to H1's rightChild Otherwise leftChild(H1) = rightChild(H1) and H1 moves to its rightChild

Otherwise work on rightChild(H1)

(Symmetric case)

Move to rightChild(H1)

If Leftist Heap Property is violated i.e If w(leftChild(H1)) < w( rightChild(H1)) then swap children and weights of H1, leftChild(H1) = H2 & Lsize(H1) = w(H2)

Otherwise rightChild(H1) = H2 & Rsize = w(H2) NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞ 3

Header Node

2

2

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

Merge the two min weight-biased leftist heaps NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞ 3

Header Node

2

2

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

Since data(H1) '18' > data(H2) '19' Swap the two NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞ 7

Header Node

2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Merge the two min weight-biased leftist heaps NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞ 3

Header Node

2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

H1 '9' now becomes rightChild of Header node Rsize(Header Node) = '3' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 3 2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

H1 '9' now becomes rightChild of Header node Rsize(Header Node) = '3' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 3 2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Since data(H2) '18' > data(H1) '9' and w(H2) + Rsize(Header) = 6 NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Rsize(Header Node) = '6' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6

1+3=4

2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Since Lsize(H1) '1' < Rsize(H1) + w(H2) '4' Leftist Property is violated NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 7 2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Swap children of H1 NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

0 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Swap children of H1 NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 7 2

2

4 9 1

1 18 1

1

1

1

1

0 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Work on left of H1 — Compare data(H1) '12' and data(H2) '18' Since data(H1) < data(H2) — H1 moves to its rightChild 'NULL' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

0+3=3

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Since rightChild(H1) is 'NULL' and attaching H2 to right of H1 violates Leftist Property — Lsize(H1) = 3 NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

0+3=3

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

w(rightChild(H1)) = '4' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

w(rightChild(H1)) = '4' NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

Merge Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞

Header Node

6 2 4 9 1

1

1

3 12 0

0 14 0

2 1 18 1 1

1

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

Merge ∞ -∞

Header Node

6 2 4 9 1

1

1

3 12 0

0 14 0

2 1 18 1 1

1

1 0 29 0

1 0 25 0

Bottom Node

∞

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

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 ∞ -∞ 7

Header Node

7 3 7 3 3

3

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞ 7

Header Node

3 3 7 3 2

2

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

Delete '7' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞ 3

Header Node

2

2

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

Since data(H1) '18' > data(H2) '19' Swap the two NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞ 3

Header Node

2

2

1 18 1

1 9 1

1

1

1

1

0 29 0

0 25 0

0 14 0

0 12 0

Bottom Node

∞

Merge the two min weight-biased leftist heaps NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞ 7

Header Node

2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

H1 '9' now becomes rightChild of Header node Rsize(Header Node) = '3' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞ 3

Header Node

2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

H1 '9' now becomes rightChild of Header node Rsize(Header Node) = '3' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 3 2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Since data(H2) '18' > data(H1) '9' and w(H2) + Rsize(Header) = 6 NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 3 2

2

1 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Rsize(Header Node) = '6' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Since Lsize(H1) '1' < Rsize(H1) + w(H2) '4' Leftist Property is violated NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6

1+3=4

2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 7 2

2

4 9 1

1 18 1

1

1

1

1

0 14 0

0 12 0

0 29 0

0 25 0

Bottom Node

∞

Swap children of H1 NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

0 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Swap children of H1 NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 7 2

2

4 9 1

1 18 1

1

1

1

1

0 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Work on left of H1 — Compare data(H1) '12' and data(H2) '18' Since data(H1) < data(H2) — H1 moves to its rightChild 'NULL' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

0+3=3

∞ -∞ 6 2

2

4 9 1

1 18 1

1

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

Since rightChild(H1) is 'NULL' and attaching H2 to right of H1 violates Leftist Property — Lsize(H1) = '3' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

0+3=3

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

w(rightChild(H1)) = '4' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

w(rightChild(H1)) = '4' NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin Header Node

∞ -∞ 6 2

2

4 9 1

1 18 1

4

1

1

1

3 12 0

0 14 0

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞

Header Node

6 2 4 9 1

1

1

3 12 0

0 14 0

2 1 18 1 1

1

0 29 0

0 25 0

Bottom Node

∞

H2 becomes leftChild(H1) NUCES-FAST • Advanced Data Structures • Spring 2007

DeleteMin ∞ -∞

Header Node

6 2 4 9 1

1

1

3 12 0

0 14 0

2 1 18 1 1

1

1 0 29 0

1 0 25 0

Bottom Node

∞

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

Height-Biased vs. Weight-Biased Leftist Heaps • Insert and Delete • 2 passes: – top-down & – bottom-up (to adjust npl)

• Insert and Delete • Single pass – Top-down

NUCES-FAST • Advanced Data Structures • Spring 2007