ee is biased to get deep toward the left.
0
§6 Leftist Heap
【Theorem】: a leftist tree with r nodes on the right path must have at least 2r-1 nodes. Induction:
§7 Skew Heaps
-- a simple version of the leftist heaps
Target : Any M consecutive operations take at
most O(M log N) time.
Merge: Always swap the left and right children except that the
Home work:
p.183 5.24 Insertions
This tree has at least 2r-1 nodes
root
r+1 nodeThis on the right tree has path at least 2r-1 nodes
left subtree
right subtree
r node on the right path right subtree right subtree
12
24 33
26
26
3 6 7 24 37 33 18 8 18 17 26 7 37 18 33 12 24 21 23 10 14
Merge (iterative version):
3 10 21 23 14 26 8 17 18 12 6
H1
H2
§7 Skew Heaps
Note:
Skew heaps have the advantage that no extra space is required to maintain path lengths and no tests are required to determine when to swap children. It is an open problem to determine precisely the expected right path length of both leftist and skew heaps.
Step 2: Swap children if necessary
3 18 6 7 21 23 10 14
Home work: 12
5.16 18 24 8 37 33 heaps 17 18 two given leftist Step 1: Sort Merge the right paths without
at least r node on the right path
§6 Leftist Heaps
Discussion 6: How long is the right path of a leftist tree of N nodes? What does this conclusion mean to us?
Note: Npl(X) = min { Npl(C) + 1 for all C as children of X } 【Definition】The leftist heap property is that for every node
X in the heap, the null path length of the left child is at least as large as that of the right child. 1 1 0 0 0 0 1
Merge1 („6‟, „ 8‟)
7 37 24 8 17
7 37 18
18
Merge („7‟, „ 8‟) Merge1 („7‟, „ 8‟)
33 26
§6 Leftist Heaps
Merge (iterative version):
3 10 21 23 14 26 8 17 18 33 12 24 37 6 7
Trouble makers: Insert and Merge
Note: Insertion is merely a special case of merging.
§6 Leftist Heaps
Declaration:
struct TreeNode { ElementType PriorityQueue PriorityQueue int };
Order Property – the same Structure Property – binary tree, but unbalanced
§6 Leftist Heaps
【Definition】The null path length, Npl(X), of any node X is
the length of the shortest path from X to a node without two children. Define Npl(NULL) = –1.
Merge (recursive version):
3 10 21 23 14 26 8 17 18 33 12 24 37 6 7
37 18
Step 3:
H1
H2
Swap(H1->Right, H1->Left ) if necessary
§6 Leftist Heaps
PriorityQueue Merge ( PriorityQueue H1, PriorityQueue H2 ) { if ( H1 == NULL ) return H2; if ( H2 == NULL ) return H1; if ( H1->Element < H2->Element ) return Merge1( H1, H2 ); else return Merge1( H2, H1 ); } static PriorityQueue Merge1( PriorityQueue H1, PriorityQueue H2 ) { if ( H1->Left == NULL ) /* single node */ H1->Left = H2; /* H1->Right is already NULL and H1->Npl is already 0 */ else { H1->Right = Merge( H1->Right, H2 ); /* Step 1 & 2 */ if ( H1->Left->Npl < H1->Right->Npl ) SwapChildren( H1 ); /* Step 3 */ H1->Npl = H1->Right->Npl + 1; } /* end else */ return H1; } T = O(log N)
Step 1:
Merge( H1->Right, H2 )
12
6 7 24 33 8 17 26 18 37
Element; Left; Right; Npl;
18
Step 2:
Attach( H2, H1->Right )
3 10 21 14 23 18 18 33 12 24 8 17 26 6 7
Merge („8‟, „ 6‟)
„8‟->Right = Merge(„NULL‟, „ 18‟)
Merge1 („8‟, „ 18‟) Merge (NULL, „ 18‟)
Return ‟1 8‟
„3‟->Right = Merge(„8‟, „ 6‟)
6 12
„6‟->Right = Merge(„7‟, „ 8‟)
H1
changing their left children
3 10 21 23 14 18 33 26 12 24 37 6
p.181 H2
p.183 5.22
26
DeleteMin: BuildHeap in O(N)
7 8 17 18
Step 1: Delete the root
Step 2: Merge the two
subtrees
Tp = O(log N)
§6 Leftist Heap
Insertion routine
PriorityQueue Insert1( ElementType X, PriorityQueue H) { PriorityQueue SingleNode; SingleNode = malloc(sizeof(struct TreeNode)); if (SingleNode == NULL) FatalError(“ out of space!!!”); else { SingleNode->Element = X; SingleNode->Npl = 0; SingleNode->left = SingleNode->Right = NULL; H = Merge(SingleNode, H); } return H; }
largest of all the nodes on the right paths does not have its children swapped. No Npl.
3 10 21 23 14 26 8 17 18 33 12 24 37 6 7 18 8
Not really a special 6 but a natural 10 case, 7stop in the 12 recursions. 21 14