Height-biased Leftist Heaps Advanced)
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Height-biased Leftist Heaps Advanced) as PDF for free.
More details
- Words: 4,281
- Pages: 91
Height-biased Leftist Heaps Rabea Aden Friday, 1st May, 2007
NUCES-FAST • Advanced Data Structures • Spring 2007
Leftist Tree • Invented by Clark Allan Crane • A Leftist Tree is a priority queue • It satisfies the leftist structural property For any node X Є Leftist Tree, Rightmost path is the Shortest
Null Path Length • denoted by npl(X) • Length of shortest path from X to an external node npl(NULL) = -1 If X has zero or one child, npl(X) = 0 Otherwise npl(X) = 1 + min { npl(leftChild(X)), npl(rightChild(X))}
Null Path Length 1
1
0
0
0
0
-1 -1
0 -1 0
Null Null Null -1 -1 Null Null
-1 Null
-1 Null -1 Null
npl(NULL) = -1
-1 Null
if X has zero or one child npl(X) = 0 else npl(X) = 1 + min{ npl( leftChild(X) ), npl( rightChild(X) ) }
Structural Property •
Height-biased Leftist Property ∀ X ∈ HBLT npl(leftChild(X)) ≥ npl(rightChild(X))
• • • •
Tree is unbalanced Biased towards left Left paths are long, giving the name Leftist Tree Rightmost path is the shortest
Structural Property T1
T2
2
2
1 0
1 0
1
0
0 0
0
1* 0
0
Leftist Heap Property Violated npl(leftChild) < npl(rightChild)
1 0
Null path lengths: T1 is a Height-biased Leftist Tree, T2 is not
Leftist Heap • A Heap-ordered Leftist Tree
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
Binary Heap vs. Leftist Heap Binary Heap
Leftist Heap
— Perfectly balanced
— Very unbalanced
Operations
Binary Heap
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)
Binary Heap vs. Leftist Heap Binary Heap
Leftist Heap
— Perfectly balanced
— Very unbalanced
Operations
Binary Heap
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
Theorem The number of nodes N in a leftist tree with r nodes on the right path is ≥ 2r -1 Proof is by Induction
This gives N ≥ 2r − 1 ⇒ r ≤ log2 (n + 1)
Structure of a Node
Left Data Pointer
NPL
Right Pointer
Apart from data, left and right pointers, each node also contains the null path length
Design • A Leftist Tree is a priority queue implemented using a variant of the Binary Tree Extended Binary Tree
• A pointer to the root of the leftist tree is also maintained
Extended Binary Tree Given: A Binary Tree TB For all empty subtrees є TB replace each empty subtree with an external node
Binary Tree Internal Node
Replace each empty subtree with an external node
Extended Binary Tree Since an External Node represents NULL
npl(External Node) = -1
1
1
0
0
-1
0
-1 -1
-1
Internal Node
0
0
-1 -1
-1
0
-1
-1
External Node
Replace each empty subtree with an external node The number outside each node X is the npl(X)
Operations • • • • •
BuildHeap FindMin Merge Insert DeleteMin
O(N) O(1) O(log N) O(log N) O(log N)
General Idea • All insertions and merges are performed on the rightmost path containing at most log2 (n + 1) nodes • This may violate Leftist Heap Property • Leftist Heap Property can be easily restored
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
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 leftChild(H1) is NULL then leftChild(H1) = H2 Otherwise, Recursively Merge rightChild(H1) and H2 If Leftist Heap Property is violated i.e If npl( leftChild(H1) ) < npl( rightChild(H1) ) then swap children of H1 npl(H1) = npl(rightChild(H1)) + 1
Merge H1 & H2 H2
H1 2
2
2
3
1
1
1
1
6
9
5
8
0
0
0
0
0
0
0
0
7
13
17
37
15
11
19
23
0
0
0
41
29
26
Both H1 and H2 are Min Leftist Heaps
Merge H1 & H2 H2 H2
H1 H1 22
2
Both H1 and H2 are not NULL
2
3
11
11
1
1
6
9
5
8
00
00
00
00
0
0
0
0
7
13
17
37
15
11
19
23
00
0
0
41
29
26
Merge (H1, H2) Compare root(H1) '2' & root(H2) '3' — H1 has smaller root
Merge H1 & H2 H2
H1 22
2
2
3
H1
1
1
1
1
6
9
5
8
00
0
00
00
0
0
0
0
7
13
17
37
15
11
19
23
00
0
0
41
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
Both H1 and H2 are not NULL
2
3
H1
1
1
1
1
6
9
5
8
0
0
0
0
0
0
0
0
7
13
17
37
15
11
19
23
0
0
0
41
29
26
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
Merge H1 & H2 H2 2
1
2 1
22
6
3
0
0
7
13 0 0
15 15
1 1
5 5
9
H1
11 11
0 0
0 0
19 19
29 29
Resizing H1
0
17
37 0
1 1
0 0
0
41
8 8
0 0
23 23
0 0
26 26
Merge H1 & H2 H2 2
1
2
0
7
1
2
6
3 1
1
13 5
8
0
9
H1
0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
0
7
1
2
6
3
H1
1
1
13 5
8
0
1
Both H1 and H2 are not NULL
9 0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Merge (H1, H2) Compare root(H1) '8' & root(H2) '9' — H1 has smaller root
Merge H1 & H2 H2
0
7
2
1
2
9
1
2
6
3
H1
1
1
13 5
8
0
0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
0
7
1
2
6
3 1
1
13 5
8
0
1
Both H1 and H2 are not NULL
9
0 091H2 17 37410
0
0
17
37 0
H1
0
0
0
0
15
11
19
23
0
0
29
26
41
Merge (H1, H2) Compare root(H1) '23' & root(H2) '9' — H2 has smaller root swap(H1, H2) Now, root(H1) = '9' & root(H2) = '23'
Merge H1 & H2 H2
0
7
2
0
2
23
1
2
6
3
0
26
1
1
13 5
8
0
H1
0
0
0
1
15
11
19
9
0 0
2929
0
0
17
37 0
41
Resizing H1
0 091H2 17 37410
Merge H1 & H2 H2
0
7
2
0
2
23
1
2
6
3
0
26
1
1
13 5
8
0
H1
0
0
0
1
15
11
19
9
0
0
0
29
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
0 091H2 17 37410
Merge H1 & H2 H2 2
2
0
7
1
2
6
3
23
0 091H2 17 37410
0
26
1
1
13 5
8
0
0
Both H1 and H2 are not NULL
0
0
0
1
15
11
19
9
H1
0
0
29
0
17
37 0
41
Merge (H1, H2) Compare root(H1) '37' & root(H2) '23' — H2 has smaller root swap(H1, H2) Now, root(H1) = '23' & root(H2) = '37'
Merge H1 & H2 H2
0
7
2
0
2
37
1
2
6
3
0
41
1
1
13 5
8
0
0
0
0
1
15
11
19
9
H1
0
0
0
29
17
23 0
26
NULL
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild — NULL
0 091H2 17 37410
Merge H1 & H2 H2
2
2
0
7
1
2
6
3
37 0
41
1
1
13 5
8
0
0
H1 is NULL
0
0
0
1
15
11
19
9
0
0
0
29
17
23
H1
0
26
NULL
Merge (H1, H2) Since root(H1) is 'NULL' swap(H1, H2) Now, root(H1) = '37' & root(H2) = 'NULL'
Merge H1 & H2 H2
2
H2 is NULL
2
0
7
NULL
1
2
6
3 1
1
13 5
8
0
0
0
0
1
15
11
19
9
0
0
0
29
17
23 0
Adjust Null Path Lengths from the Last Node on the Rightmost Path to the Root H1
0
26 37 0
41
NULL
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3 1
1
13 5
8
0 0
15
Adjust Null Lengths H1Path points to '37' 0 1 0 from the Last Node 11 19 9 on the Rightmost Path 0 0 0 to the Root H1 29 17 23 00
0
26 37 00
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
NULL
npl (NULL) = -1
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
1
15
11
19
9
H1 moves up to '23'
0
0
29
0 10*
17
23
H1 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
NULL
npl (NULL) = -1
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
1* 1
15
11
19
9
0
0
29
17
H1 moves up to '9' H1
11
23 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
15
11
19 0
29
H1
H1 moves up to '9'
11* 9 0
1
17
23 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 0
11* 1
1
13 5
8
H1
0
0
00
11
15
11
19
9
H1 moves up to '8'
0 0
11
0 0
2929
23
17 17 00
00
37 26 37 26 00
41 41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3
H1
1
11
13 5
8
0
0
0
1 0
0
15
11
9
19
1
0
17 29
23 0
0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ 1 H1→npl = rightChild(H1)→npl + 1 = '2'
H1 moves up to '3'
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2* 2 2
2
0
7
H1
1
2
6
3 1
1
13 5
8
0
0
0
0
0
15
11
9
19
1
0
17 29
23 0
0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≤ 2 H1→npl = rightChild(H1)→npl + 1 = '2'
H1 moves up to '2'
Merge H1 & H2 H1
Root
22 2 2
1
3
6
1
1
0
0
5
8
7
13
0
0
0
0
15
11
9
19
1
0
17 29
23 0
0
26 37 0
41
0
H1 is returned Root pointer now points to H1
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 Leftist Heap Property is violated i.e If npl( leftChild(X) ) < npl( rightChild(X) ) then swap children of X npl(X) = npl(rightChild(X) + 1
Time Complexity of Merge • O(log n) • As only shortest path is traversed
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
Insert 3 H1
H2 2
0
2
3
1
1
6
9
0
0
0
0
7
13
17
37 0
41
H1 — existing Heap H2 — one-node heap containing node to be inserted Both H1 and H2 are Min Leftist Heaps
Insert 3 H1 H1
H2 22
Both H1 and H2 are not NULL
2 11
11
6
9
00
00
00
00
7
13
17
37
0
3
00
41
Merge (H1, H2) Compare root(H1) '2' & root(H2) '3' — H1 has smaller root
Insert 3 H1
H2 2
0
2
H1
1
1
6
9
0
0
0
0
7
13
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
3
Insert 3 H2 2
Both H1 and H2 are not NULL
2
H1
1
1
6
9
0
0
0
0
7
13
17
37
0
3
0
41
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
Insert 3 H2 22
1
2
9
H1
11
00
6
33
0
0
17
37
00
00
1
0
7
13
9 NULL
41
0
0
17
37 0
41
Since, leftChild(H1) == NULL leftChild(H1) = H2
Insert 3 H2 2
Adjust Null Path Lengths 2 from the last node 1 0 on the Rightmost Path 6 3 to the Root 0
0
1
7
13
9 0
0
17
37 0
41
H2 is NULL H1
NULL
Insert 3 2
Adjust Null Path Lengths from the last node on the Rightmost Path to the Root
2
H1
1
0
6
3
0
0
1
7
13
9
Leftist Heap Property NOT Violated
NULL
0
0
17
37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
H1 points to '3'
npl (NULL) = -1
Insert 3 2 12*
2
H1
1
0
6
3
0
0
1
7
13
9
Leftist Heap Property NOT Violated
NULL
0
0
17
37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
H1 moves up to '2'
npl (NULL) = -1
Insert 3 H1
Root
11 2 1
0
6
3
0
0
1
7
13
9 0
0
17
37 0
41
H1 is returned Root pointer now points to H1
Time Complexity of Insert • O(log n) • Create a one-node heap — O(1) • Merge — O(log n) – As only shortest path is traversed
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
DeleteMin Root 2
2 1
1
6
9
0
0
0
0
7
13
17
37 0
41
Delete Minimum Key '2'
DeleteMin oldRoot Root 22
22
H1
H2
1
1
6
9
0
0
0
0
7
13
17
37 0
41
Save old value of root H1 = root→leftChild H2 = root→rightChild
DeleteMin oldRoot 2
2
H1 1
H2
Both H1 and H2 are not NULL
6
1
9
0
0
0
0
7
13
17
37 0
41
Merge (H1, H2) Compare root(H1) '6' & root(H2) '9' — H1 has smaller root
DeleteMin oldRoot 2
2
H1
H2
1
1
6
9
H1
0
0
0
0
7
13
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
DeleteMin oldRoot 2
2 1
H2
Both H1 and H2 are not NULL
6
H1
1
9
0
0
0
0
7
13
17
37 0
41
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
DeleteMin oldRoot 2
2
H2 0
1
6
H1
0
1
7
9 0
0
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
13
DeleteMin oldRoot 2
2 1
Both H1 and H2 are not NULL
6 0
1
7
9
H2 0
13
H1
0
0
17
37 0
41
Merge (H1, H2) Compare root(H1) '37' & root(H2) '13' — H2 has smaller root swap(H1, H2) Now, root(H1) = '37' & root(H2) = '13'
DeleteMin oldRoot 2
2
H2
1
0
6
37
0
1
7
9
0 H1
0
0
17
13 0
37 NULL 0
41
Since, leftChild(H1) == NULL leftChild(H1) = H2
41
DeleteMin oldRoot 2
Adjust Null Path Lengths from the last node 1 on the Rightmost Path 6 to the Root 0
1
7
9
2
H2 is NULL H1
0
0
17
13 0
37 0
41
H2
NULL
DeleteMin oldRoot 2
Adjust Null Path Lengths from the last node on the Rightmost Path to the Root
2
H1 points to '13'
1
6 0
1
7
9
Leftist Heap Property NOT Violated
H1
0
0
17
13 0
37
NULL
0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
npl (NULL) = -1
DeleteMin oldRoot 2
2
H1 moves up to '9'
1
6 0
1
7
9
Leftist Heap Property NOT Violated
H1
0
0
17
13 0
37
NULL
0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
npl (NULL) = -1
DeleteMin oldRoot 2
2
H1 moves up to '6'
H1
1 11*
6
H1
00
1 1
7
9 00
0 0
17 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
13 0 0
37 00
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
DeleteMin oldRoot 2
2
Root
H1
11 6 1
0
9
7
0
0
17
13 0
37 0
41
H1 is returned Root pointer now points to H1 Delete old value of Root
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
Brute Force BuildHeap • O(N logN) time Based on Insert Given N elements, create N one-node min leftist heaps and insert them into a Queue, Q Size of Q, |Q| = N Root = Remove first min leftist heap from queue while( |Q| > 0 ) Remove one min leftist heaps from queue — H Insert( H )
Brute Force BuildHeap 0
0
0
0
0
0
0
7
9
37
41
2
6
13
Build a min leftist heap containing elements 7, 9, 37, 41, 2, 6, 13 Create 7 one-node min leftist heaps and insert them in a queue — |Q| = 7
Brute Force BuildHeap H
Root 000
00
0
0
0
0
0
77
99
37
41
2
6
13
00
99
Root = 7 H=9 Insert( H )
|Q| = 6 |Q| = 5
Brute Force BuildHeap H
Root 01
00
0
0
0
0
7
37 37
41
2
6
13
0
0
9
37
Root = 7 H = 37 Insert( H )
|Q| = 5 |Q| = 4
Brute Force BuildHeap H
Root 11
0
0
0
0
7
41
2
6
13
0
0
9
37 0
41
Root = 7 H = 41 Insert( H )
|Q| = 4 |Q| = 3
Brute Force BuildHeap H
Root 1 0
00
0
0
7 2
22
6
13
11 0
0
7 9
37
00
0 0
9
37 41 00
41
Root = 7 H=2 Insert( H )
|Q| = 3 |Q| = 2
Brute Force BuildHeap H
Root 011
00
0
22
66
13
111
00
77
6
000
000
99
37 37 000
41 41
Root = 7 H=6 Insert( H )
|Q| = 2 |Q| = 1
Brute Force BuildHeap H
Root
11
11
00
2
13 13
1
0
7 7 00
0
00
6 6 0
00
9 9 37 37 13 00
0
41 41
Root = 7 H = 13 Insert( H )
|Q| = 1 |Q| = 0
00
Time Complexity of Brute Force BuildHeap • O(N log N)
1 insert — O(log N) N inserts — O(N log N)
Efficient BuildHeap • O(N) time Based on Merge Given N elements, create N one-node min leftist heaps and insert them into a Queue, Q Size of Q, |Q| = N while( |Q| > 1 ) Remove first two min leftist heaps from queue — H1 and H2 Merge H1 and H2 Insert merged min leftist heap into queue
Efficient BuildHeap 0
0
0
0
0
0
0
7
9
37
41
2
6
13
Build a min leftist heap containing elements 7, 9, 37, 41, 2, 6, 13 Create 7 one-node min leftist heaps and insert them in a queue — |Q| = 7
Efficient BuildHeap H2
H1 00
00
0
0
0
0
0
0
77
99
37
41
2
6
7
13
0
0
9
9
Remove and merge first two min leftist heaps from queue H1 = 7 |Q| = 6 H2 = 9 |Q| = 5 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 6
Efficient BuildHeap H2
H1 00
00
0
0
0
0
0
37 37
41 41
2
6
13
37
7
0
0
0
41
41
9
Remove and merge first two min leftist heaps from queue H1 = 37 |Q| = 5 H2 = 41 |Q| = 4 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 5
Efficient BuildHeap H2
H1 00
00
0
0
0
0
22
66
13
7
2
37
0
0
0
0
6
9
6
41
Remove and merge first two min leftist heaps from queue H1 = 2 |Q| = 4 H2 = 6 |Q| = 3 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 4
Efficient BuildHeap H2
H1
0
9
00 1
0
0
1
0
13 7 13
7
37
7
2
0
0
13 9
0
0
00
41
9
613
Remove and merge first two min leftist heaps from queue H1 = 13 |Q| = 3 H2 = 7 |Q| = 2 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 3
Efficient BuildHeap H2
H1 1 0
0
1
1
2 37
2
2
7
0
0
41 6
0
0
00
37 6
6
937 13
0
0
41
41
0
Remove and merge first two min leftist heaps from queue H1 = 37 |Q| = 2 H2 = 2 |Q| = 1 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 2
Efficient BuildHeap H2
H1 1
1
11
2 7
2
2
01
00
97 0
0
9
1
00 0
00
13 6 7
66
37
0
0
13 9
13 41
0
0
37
37
0
0
41
41
00
Remove and merge first two min leftist heaps from queue H1 = 7 |Q| = 1 H2 = 2 |Q| = 0 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 1
Efficient BuildHeap Root 1
2 1
0
7
6
0
0
9
13 0
37 0
41
Since |Q| > 0 Root = 2
Time Complexity of Efficient BuildHeap Assume min leftist heap contains N = 2k elements Merge Operations
N/2 N/4 N/8 ׃ ׃ N/2k = 1
Recursive Calls to Merge
1 2 3
k
Time Complexity of Efficient BuildHeap Total Time for BuildHeap = = = =
N N N N ( * 1) + ( * 2) + ( * 3) + + ( k * k) 2 4 8 2 1 1 1 1 N( + + + k) 2 4 8 2 k i N∑ i i=1 2 ∞ i N∑ i i=1 2
= 3n for n ≥ 3 = Ο(N)
NUCES-FAST • Advanced Data Structures • Spring 2007
Leftist Tree • Invented by Clark Allan Crane • A Leftist Tree is a priority queue • It satisfies the leftist structural property For any node X Є Leftist Tree, Rightmost path is the Shortest
Null Path Length • denoted by npl(X) • Length of shortest path from X to an external node npl(NULL) = -1 If X has zero or one child, npl(X) = 0 Otherwise npl(X) = 1 + min { npl(leftChild(X)), npl(rightChild(X))}
Null Path Length 1
1
0
0
0
0
-1 -1
0 -1 0
Null Null Null -1 -1 Null Null
-1 Null
-1 Null -1 Null
npl(NULL) = -1
-1 Null
if X has zero or one child npl(X) = 0 else npl(X) = 1 + min{ npl( leftChild(X) ), npl( rightChild(X) ) }
Structural Property •
Height-biased Leftist Property ∀ X ∈ HBLT npl(leftChild(X)) ≥ npl(rightChild(X))
• • • •
Tree is unbalanced Biased towards left Left paths are long, giving the name Leftist Tree Rightmost path is the shortest
Structural Property T1
T2
2
2
1 0
1 0
1
0
0 0
0
1* 0
0
Leftist Heap Property Violated npl(leftChild) < npl(rightChild)
1 0
Null path lengths: T1 is a Height-biased Leftist Tree, T2 is not
Leftist Heap • A Heap-ordered Leftist Tree
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
Binary Heap vs. Leftist Heap Binary Heap
Leftist Heap
— Perfectly balanced
— Very unbalanced
Operations
Binary Heap
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)
Binary Heap vs. Leftist Heap Binary Heap
Leftist Heap
— Perfectly balanced
— Very unbalanced
Operations
Binary Heap
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
Theorem The number of nodes N in a leftist tree with r nodes on the right path is ≥ 2r -1 Proof is by Induction
This gives N ≥ 2r − 1 ⇒ r ≤ log2 (n + 1)
Structure of a Node
Left Data Pointer
NPL
Right Pointer
Apart from data, left and right pointers, each node also contains the null path length
Design • A Leftist Tree is a priority queue implemented using a variant of the Binary Tree Extended Binary Tree
• A pointer to the root of the leftist tree is also maintained
Extended Binary Tree Given: A Binary Tree TB For all empty subtrees є TB replace each empty subtree with an external node
Binary Tree Internal Node
Replace each empty subtree with an external node
Extended Binary Tree Since an External Node represents NULL
npl(External Node) = -1
1
1
0
0
-1
0
-1 -1
-1
Internal Node
0
0
-1 -1
-1
0
-1
-1
External Node
Replace each empty subtree with an external node The number outside each node X is the npl(X)
Operations • • • • •
BuildHeap FindMin Merge Insert DeleteMin
O(N) O(1) O(log N) O(log N) O(log N)
General Idea • All insertions and merges are performed on the rightmost path containing at most log2 (n + 1) nodes • This may violate Leftist Heap Property • Leftist Heap Property can be easily restored
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
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 leftChild(H1) is NULL then leftChild(H1) = H2 Otherwise, Recursively Merge rightChild(H1) and H2 If Leftist Heap Property is violated i.e If npl( leftChild(H1) ) < npl( rightChild(H1) ) then swap children of H1 npl(H1) = npl(rightChild(H1)) + 1
Merge H1 & H2 H2
H1 2
2
2
3
1
1
1
1
6
9
5
8
0
0
0
0
0
0
0
0
7
13
17
37
15
11
19
23
0
0
0
41
29
26
Both H1 and H2 are Min Leftist Heaps
Merge H1 & H2 H2 H2
H1 H1 22
2
Both H1 and H2 are not NULL
2
3
11
11
1
1
6
9
5
8
00
00
00
00
0
0
0
0
7
13
17
37
15
11
19
23
00
0
0
41
29
26
Merge (H1, H2) Compare root(H1) '2' & root(H2) '3' — H1 has smaller root
Merge H1 & H2 H2
H1 22
2
2
3
H1
1
1
1
1
6
9
5
8
00
0
00
00
0
0
0
0
7
13
17
37
15
11
19
23
00
0
0
41
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
Both H1 and H2 are not NULL
2
3
H1
1
1
1
1
6
9
5
8
0
0
0
0
0
0
0
0
7
13
17
37
15
11
19
23
0
0
0
41
29
26
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
Merge H1 & H2 H2 2
1
2 1
22
6
3
0
0
7
13 0 0
15 15
1 1
5 5
9
H1
11 11
0 0
0 0
19 19
29 29
Resizing H1
0
17
37 0
1 1
0 0
0
41
8 8
0 0
23 23
0 0
26 26
Merge H1 & H2 H2 2
1
2
0
7
1
2
6
3 1
1
13 5
8
0
9
H1
0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
0
7
1
2
6
3
H1
1
1
13 5
8
0
1
Both H1 and H2 are not NULL
9 0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Merge (H1, H2) Compare root(H1) '8' & root(H2) '9' — H1 has smaller root
Merge H1 & H2 H2
0
7
2
1
2
9
1
2
6
3
H1
1
1
13 5
8
0
0
0
17
37 0
41
0
0
0
0
15
11
19
23
0
0
29
26
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
Merge H1 & H2 H2 2
2
0
7
1
2
6
3 1
1
13 5
8
0
1
Both H1 and H2 are not NULL
9
0 091H2 17 37410
0
0
17
37 0
H1
0
0
0
0
15
11
19
23
0
0
29
26
41
Merge (H1, H2) Compare root(H1) '23' & root(H2) '9' — H2 has smaller root swap(H1, H2) Now, root(H1) = '9' & root(H2) = '23'
Merge H1 & H2 H2
0
7
2
0
2
23
1
2
6
3
0
26
1
1
13 5
8
0
H1
0
0
0
1
15
11
19
9
0 0
2929
0
0
17
37 0
41
Resizing H1
0 091H2 17 37410
Merge H1 & H2 H2
0
7
2
0
2
23
1
2
6
3
0
26
1
1
13 5
8
0
H1
0
0
0
1
15
11
19
9
0
0
0
29
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
0 091H2 17 37410
Merge H1 & H2 H2 2
2
0
7
1
2
6
3
23
0 091H2 17 37410
0
26
1
1
13 5
8
0
0
Both H1 and H2 are not NULL
0
0
0
1
15
11
19
9
H1
0
0
29
0
17
37 0
41
Merge (H1, H2) Compare root(H1) '37' & root(H2) '23' — H2 has smaller root swap(H1, H2) Now, root(H1) = '23' & root(H2) = '37'
Merge H1 & H2 H2
0
7
2
0
2
37
1
2
6
3
0
41
1
1
13 5
8
0
0
0
0
1
15
11
19
9
H1
0
0
0
29
17
23 0
26
NULL
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild — NULL
0 091H2 17 37410
Merge H1 & H2 H2
2
2
0
7
1
2
6
3
37 0
41
1
1
13 5
8
0
0
H1 is NULL
0
0
0
1
15
11
19
9
0
0
0
29
17
23
H1
0
26
NULL
Merge (H1, H2) Since root(H1) is 'NULL' swap(H1, H2) Now, root(H1) = '37' & root(H2) = 'NULL'
Merge H1 & H2 H2
2
H2 is NULL
2
0
7
NULL
1
2
6
3 1
1
13 5
8
0
0
0
0
1
15
11
19
9
0
0
0
29
17
23 0
Adjust Null Path Lengths from the Last Node on the Rightmost Path to the Root H1
0
26 37 0
41
NULL
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3 1
1
13 5
8
0 0
15
Adjust Null Lengths H1Path points to '37' 0 1 0 from the Last Node 11 19 9 on the Rightmost Path 0 0 0 to the Root H1 29 17 23 00
0
26 37 00
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
NULL
npl (NULL) = -1
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
1
15
11
19
9
H1 moves up to '23'
0
0
29
0 10*
17
23
H1 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
NULL
npl (NULL) = -1
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
1* 1
15
11
19
9
0
0
29
17
H1 moves up to '9' H1
11
23 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 1
1
13 5
8
0
0
0
0
15
11
19 0
29
H1
H1 moves up to '9'
11* 9 0
1
17
23 0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2
2
0
7
1
2
6
3 0
11* 1
1
13 5
8
H1
0
0
00
11
15
11
19
9
H1 moves up to '8'
0 0
11
0 0
2929
23
17 17 00
00
37 26 37 26 00
41 41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
Merge H1 & H2 Leftist Heap Property NOT Violated
2
2
0
7
1
2
6
3
H1
1
11
13 5
8
0
0
0
1 0
0
15
11
9
19
1
0
17 29
23 0
0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ 1 H1→npl = rightChild(H1)→npl + 1 = '2'
H1 moves up to '3'
Merge H1 & H2 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
2* 2 2
2
0
7
H1
1
2
6
3 1
1
13 5
8
0
0
0
0
0
15
11
9
19
1
0
17 29
23 0
0
0
26 37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≤ 2 H1→npl = rightChild(H1)→npl + 1 = '2'
H1 moves up to '2'
Merge H1 & H2 H1
Root
22 2 2
1
3
6
1
1
0
0
5
8
7
13
0
0
0
0
15
11
9
19
1
0
17 29
23 0
0
26 37 0
41
0
H1 is returned Root pointer now points to H1
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 Leftist Heap Property is violated i.e If npl( leftChild(X) ) < npl( rightChild(X) ) then swap children of X npl(X) = npl(rightChild(X) + 1
Time Complexity of Merge • O(log n) • As only shortest path is traversed
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
Insert 3 H1
H2 2
0
2
3
1
1
6
9
0
0
0
0
7
13
17
37 0
41
H1 — existing Heap H2 — one-node heap containing node to be inserted Both H1 and H2 are Min Leftist Heaps
Insert 3 H1 H1
H2 22
Both H1 and H2 are not NULL
2 11
11
6
9
00
00
00
00
7
13
17
37
0
3
00
41
Merge (H1, H2) Compare root(H1) '2' & root(H2) '3' — H1 has smaller root
Insert 3 H1
H2 2
0
2
H1
1
1
6
9
0
0
0
0
7
13
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
3
Insert 3 H2 2
Both H1 and H2 are not NULL
2
H1
1
1
6
9
0
0
0
0
7
13
17
37
0
3
0
41
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
Insert 3 H2 22
1
2
9
H1
11
00
6
33
0
0
17
37
00
00
1
0
7
13
9 NULL
41
0
0
17
37 0
41
Since, leftChild(H1) == NULL leftChild(H1) = H2
Insert 3 H2 2
Adjust Null Path Lengths 2 from the last node 1 0 on the Rightmost Path 6 3 to the Root 0
0
1
7
13
9 0
0
17
37 0
41
H2 is NULL H1
NULL
Insert 3 2
Adjust Null Path Lengths from the last node on the Rightmost Path to the Root
2
H1
1
0
6
3
0
0
1
7
13
9
Leftist Heap Property NOT Violated
NULL
0
0
17
37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
H1 points to '3'
npl (NULL) = -1
Insert 3 2 12*
2
H1
1
0
6
3
0
0
1
7
13
9
Leftist Heap Property NOT Violated
NULL
0
0
17
37 0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 1 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
H1 moves up to '2'
npl (NULL) = -1
Insert 3 H1
Root
11 2 1
0
6
3
0
0
1
7
13
9 0
0
17
37 0
41
H1 is returned Root pointer now points to H1
Time Complexity of Insert • O(log n) • Create a one-node heap — O(1) • Merge — O(log n) – As only shortest path is traversed
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
DeleteMin Root 2
2 1
1
6
9
0
0
0
0
7
13
17
37 0
41
Delete Minimum Key '2'
DeleteMin oldRoot Root 22
22
H1
H2
1
1
6
9
0
0
0
0
7
13
17
37 0
41
Save old value of root H1 = root→leftChild H2 = root→rightChild
DeleteMin oldRoot 2
2
H1 1
H2
Both H1 and H2 are not NULL
6
1
9
0
0
0
0
7
13
17
37 0
41
Merge (H1, H2) Compare root(H1) '6' & root(H2) '9' — H1 has smaller root
DeleteMin oldRoot 2
2
H1
H2
1
1
6
9
H1
0
0
0
0
7
13
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
DeleteMin oldRoot 2
2 1
H2
Both H1 and H2 are not NULL
6
H1
1
9
0
0
0
0
7
13
17
37 0
41
Merge (H1, H2) Compare root(H1) '9' & root(H2) '3' — H2 has smaller root swap(H1, H2) Now, root(H1) = '3' & root(H2) = '9'
DeleteMin oldRoot 2
2
H2 0
1
6
H1
0
1
7
9 0
0
17
37 0
41
Since, leftChild(H1) ≠ NULL H1 now points to its rightChild
13
DeleteMin oldRoot 2
2 1
Both H1 and H2 are not NULL
6 0
1
7
9
H2 0
13
H1
0
0
17
37 0
41
Merge (H1, H2) Compare root(H1) '37' & root(H2) '13' — H2 has smaller root swap(H1, H2) Now, root(H1) = '37' & root(H2) = '13'
DeleteMin oldRoot 2
2
H2
1
0
6
37
0
1
7
9
0 H1
0
0
17
13 0
37 NULL 0
41
Since, leftChild(H1) == NULL leftChild(H1) = H2
41
DeleteMin oldRoot 2
Adjust Null Path Lengths from the last node 1 on the Rightmost Path 6 to the Root 0
1
7
9
2
H2 is NULL H1
0
0
17
13 0
37 0
41
H2
NULL
DeleteMin oldRoot 2
Adjust Null Path Lengths from the last node on the Rightmost Path to the Root
2
H1 points to '13'
1
6 0
1
7
9
Leftist Heap Property NOT Violated
H1
0
0
17
13 0
37
NULL
0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ -1 H1→npl = rightChild(H1)→npl + 1 = '0'
npl (NULL) = -1
DeleteMin oldRoot 2
2
H1 moves up to '9'
1
6 0
1
7
9
Leftist Heap Property NOT Violated
H1
0
0
17
13 0
37
NULL
0
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≥ 0 H1→npl = rightChild(H1)→npl + 1 = '1'
npl (NULL) = -1
DeleteMin oldRoot 2
2
H1 moves up to '6'
H1
1 11*
6
H1
00
1 1
7
9 00
0 0
17 Leftist Heap Property Violated swap( leftChild(H1), rightChild(H1) )
13 0 0
37 00
41
leftChild(H1)→npl ≥ rightChild(H1)→npl — 0 ≤ 1 H1→npl = rightChild(H1)→npl + 1 = '1'
DeleteMin oldRoot 2
2
Root
H1
11 6 1
0
9
7
0
0
17
13 0
37 0
41
H1 is returned Root pointer now points to H1 Delete old value of Root
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
Brute Force BuildHeap • O(N logN) time Based on Insert Given N elements, create N one-node min leftist heaps and insert them into a Queue, Q Size of Q, |Q| = N Root = Remove first min leftist heap from queue while( |Q| > 0 ) Remove one min leftist heaps from queue — H Insert( H )
Brute Force BuildHeap 0
0
0
0
0
0
0
7
9
37
41
2
6
13
Build a min leftist heap containing elements 7, 9, 37, 41, 2, 6, 13 Create 7 one-node min leftist heaps and insert them in a queue — |Q| = 7
Brute Force BuildHeap H
Root 000
00
0
0
0
0
0
77
99
37
41
2
6
13
00
99
Root = 7 H=9 Insert( H )
|Q| = 6 |Q| = 5
Brute Force BuildHeap H
Root 01
00
0
0
0
0
7
37 37
41
2
6
13
0
0
9
37
Root = 7 H = 37 Insert( H )
|Q| = 5 |Q| = 4
Brute Force BuildHeap H
Root 11
0
0
0
0
7
41
2
6
13
0
0
9
37 0
41
Root = 7 H = 41 Insert( H )
|Q| = 4 |Q| = 3
Brute Force BuildHeap H
Root 1 0
00
0
0
7 2
22
6
13
11 0
0
7 9
37
00
0 0
9
37 41 00
41
Root = 7 H=2 Insert( H )
|Q| = 3 |Q| = 2
Brute Force BuildHeap H
Root 011
00
0
22
66
13
111
00
77
6
000
000
99
37 37 000
41 41
Root = 7 H=6 Insert( H )
|Q| = 2 |Q| = 1
Brute Force BuildHeap H
Root
11
11
00
2
13 13
1
0
7 7 00
0
00
6 6 0
00
9 9 37 37 13 00
0
41 41
Root = 7 H = 13 Insert( H )
|Q| = 1 |Q| = 0
00
Time Complexity of Brute Force BuildHeap • O(N log N)
1 insert — O(log N) N inserts — O(N log N)
Efficient BuildHeap • O(N) time Based on Merge Given N elements, create N one-node min leftist heaps and insert them into a Queue, Q Size of Q, |Q| = N while( |Q| > 1 ) Remove first two min leftist heaps from queue — H1 and H2 Merge H1 and H2 Insert merged min leftist heap into queue
Efficient BuildHeap 0
0
0
0
0
0
0
7
9
37
41
2
6
13
Build a min leftist heap containing elements 7, 9, 37, 41, 2, 6, 13 Create 7 one-node min leftist heaps and insert them in a queue — |Q| = 7
Efficient BuildHeap H2
H1 00
00
0
0
0
0
0
0
77
99
37
41
2
6
7
13
0
0
9
9
Remove and merge first two min leftist heaps from queue H1 = 7 |Q| = 6 H2 = 9 |Q| = 5 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 6
Efficient BuildHeap H2
H1 00
00
0
0
0
0
0
37 37
41 41
2
6
13
37
7
0
0
0
41
41
9
Remove and merge first two min leftist heaps from queue H1 = 37 |Q| = 5 H2 = 41 |Q| = 4 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 5
Efficient BuildHeap H2
H1 00
00
0
0
0
0
22
66
13
7
2
37
0
0
0
0
6
9
6
41
Remove and merge first two min leftist heaps from queue H1 = 2 |Q| = 4 H2 = 6 |Q| = 3 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 4
Efficient BuildHeap H2
H1
0
9
00 1
0
0
1
0
13 7 13
7
37
7
2
0
0
13 9
0
0
00
41
9
613
Remove and merge first two min leftist heaps from queue H1 = 13 |Q| = 3 H2 = 7 |Q| = 2 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 3
Efficient BuildHeap H2
H1 1 0
0
1
1
2 37
2
2
7
0
0
41 6
0
0
00
37 6
6
937 13
0
0
41
41
0
Remove and merge first two min leftist heaps from queue H1 = 37 |Q| = 2 H2 = 2 |Q| = 1 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 2
Efficient BuildHeap H2
H1 1
1
11
2 7
2
2
01
00
97 0
0
9
1
00 0
00
13 6 7
66
37
0
0
13 9
13 41
0
0
37
37
0
0
41
41
00
Remove and merge first two min leftist heaps from queue H1 = 7 |Q| = 1 H2 = 2 |Q| = 0 H1 = Merge(H1, H2) Insert H1 into queue |Q| = 1
Efficient BuildHeap Root 1
2 1
0
7
6
0
0
9
13 0
37 0
41
Since |Q| > 0 Root = 2
Time Complexity of Efficient BuildHeap Assume min leftist heap contains N = 2k elements Merge Operations
N/2 N/4 N/8 ׃ ׃ N/2k = 1
Recursive Calls to Merge
1 2 3
k
Time Complexity of Efficient BuildHeap Total Time for BuildHeap = = = =
N N N N ( * 1) + ( * 2) + ( * 3) + + ( k * k) 2 4 8 2 1 1 1 1 N( + + + k) 2 4 8 2 k i N∑ i i=1 2 ∞ i N∑ i i=1 2
= 3n for n ≥ 3 = Ο(N)
Related Documents
Weight-biased Leftist Heaps Advanced)
November 2019 9
Height-biased Leftist Heaps Advanced)
November 2019 10
Skew Heaps Advanced)
November 2019 18
Fib Heaps
November 2019 12
(politics)leftist
November 2019 7