Leftist Heaps

• There are quite a few ways of implementing heaps so that the running time of a merge is O(log N)
• Leftist Heap


  A binary tree data structure that efficiently supports merging

  
• Leftist Heap


  • Has a structural property and an ordering property
  • Has the same heap-order property as a binary heap
  • Is a binary tree that is not perfectly balanced but attempts to be very unbalanced
• Null Path Length (npl(X))


  The length of the shortest path from node X to a node without two children
• The null path length of any node is 1 more than the minimum of the null path lengths of its children
• Leftist Heap Property


  For every node X, the null path length of the left child is at least as large as that of the right child
• A leftist tree with r nodes on the right path must have at least 2^r - 1 nodes
• A leftist tree of N nodes has a right path containing at most log(N + 1) nodes
• Leftist Heap Operations


  1. Merging

  2. Insertion (a special case of merging)
• The fundamental operation on leftist heaps is merging
• Insertion is merely a special case of merging, since we may view an insertion as a merge of a one-node heap with a larger heap
• The resulting tree after merging two leftist heaps is a leftist heap
• To make the resulting tree leftist after merging, we need to swap the root's left and right children and update the null path length
• The description of the leftist heap merging algorithm translates directly into code
• Description of the algorithm

  1. Translates directly into code

  2. Node class is the same as the binary tree, except that it is augmented with the npl (null path length) field

  3. Leftist heap stores a reference to the root as its data member

  4. Recursive methods used to do the merging

  
• Merge routines

  1. Drivers designed to remove special cases and ensure that H1 has the smaller root

  2. Actual merging performed in merge1 (Figure 6.27)

  3. Public merge method merges rhs into the controlling heap, rhs becomes empty

  4. Alias test in public method disallows h.merge(h)
• Time to perform the merge is proportional to the sum of the length of the right paths, because constant work is performed at each node visited during the recursive calls
• Merge can also be performed nonrecursively by essentially performing two passes
• Insertions can be carried out by making the item to be inserted a one-node heap and performing a merge
• To perform a deleteMin, we merely destroy the root, creating two heaps, which can then be merged
• Time to perform a deleteMin is O(log N)
• Leftist heap can be built in O(N) time by building a binary heap
• Traversing the tree in reverse-level order is not as easy with links
• Leftist heap can be built recursively by building the left and right subtrees and then percolating the root down