Leftist Heap

                                 

                   Priority Queues:Leftist Heaps

New Heap Operation: Merge

Given two heaps, merge them into one heap

– first attempt: insert each element of the smaller into the larger. runtime:

– second attempt: concatenate binary heaps’ arrays and run buildHeap. runtime:

 Leftist Heaps Idea:

 Focus all heap maintenance work in one small part of the heap Leftist heaps:

 1. Binary trees

 2. Most nodes are on the left

 3. All the merging work is done on the right

Definition: Null Path Length

null path length (npl) of a node x = the number of nodes between x and a null in its subtree

                                                      OR

npl(x) = min distance to a descendant with 0 or 1 children 

Definition: Null Path Length • npl(null) = -1 • npl(leaf) = 0 • npl(single-child node) = 0

Equivalent definition: npl(x) = 1 + min{npl(left(x)), npl(right(x))}

Another useful definition: npl(x) is the height of the largest perfect binary tree that is both itself rooted at x and contained within the subtree rooted at x.

Leftist Heap Properties 

*Order property – parent’s priority value is ≤ to childrens’ priority values – result: minimum element is at the root  – (Same as binary heap) 

* Structure property – For every node x, npl(left(x)) ≥ npl(right(x)) – result: tree is at least as “heavy” on the left as the right (Terminology: we will say a leftist heap’s tree is a leftist tree) 

Observations 

Are leftist trees always… – complete? – balanced? Consider a subtree of a leftist tree… – is it leftist

Right Path in a Leftist Tree is Short (#1) 

Claim:The right path (path from root to rightmost leaf) is as short as and in the tree. 

Proof: (By contradiction) R x L D2 D1 Pick a shorter path: D1 < D2 Say it diverges from right path at x npl(L) ≤ D1-1 because of the path of length D1-1 to null npl(R) ≥ D2-1 because every node on right path is leftist Leftist property at x violated!

Right Path in a Leftist Tree is Short (#2):

Claim:If the right path has r nodes, then the tree has at least 2r-1 nodes. 

Proof: (By induction) Base case : r=1. Tree has at least 21-1 = 1 node Inductive step : assume true for r-1. Prove for tree with right path at least r. 1. Right subtree: right path of r-1 nodes ⇒ 2r-1-1 right subtree nodes (by induction) 2. Left subtree: also right path of length at least r-1 (prev. slide) ⇒ 2r-1-1 left subtree nodes (by induction) ⇒ Total tree size: (2r-1-1) + (2r-1-1) + 1 = 2r-1 

Why do we have the leftist property?

 Because it guarantees that: • the right path is really short compared to the number of nodes in the tree • A leftist tree of N nodes, has a right path of at most log2(N+1) nodes Idea – perform all work on the right path

Merge two heaps (basic idea)

 • Put the root with smaller value as the new root. • Hang its left subtree on the left.

 • Recursively merge its right subtree and the other tree.

 • Before returning from recursion: – Update npl of merged root. – Swap left and right subtrees just below root, if needed, to keep leftist property of merged result.  

Merging two leftist heaps:

Recursive calls to merge(T1,T2): returns one leftist heap containing all elements of the two (distinct) leftist heaps T1 and T2

Merge continued

Leftest Merge example

Sewing up the example

Operations on Leftist Heaps 

• merge with two trees of total size n: O(log n) 

• insert with heap size n: O(log n) – pretend node is a size 1 leftist heap – insert by merging original heap with one node heap 

• deleteMin with heap size n: O(log n) – remove and return root – merge left and right subtrees