Leftist Heaps

Donald E. Knuth was the first to suggest that the Hu-Tucker algorithm could be implemented using a leftist tree as a priority queue data structure. The following brief presentation of leftist heaps is based on the [Knu73b], and [Tar83]. A leftist heap is an extended binary tree. Every node of the leftist tree must at least have a key field, a rank field, and two pointers left, and right for the left and right subheaps or null when the element is a leaf node. The rank of a node is the shortest path from the node to a leaf node. For every node P of the leftist heap the following conditions must hold:

$P.key \leq$ (P.left).key, $P.key \leq$ (P.right).key;

P.rank = 1 + min( (P.left).rank, (P.right).rank );

$(P.left).rank \geq (P.right).rank$;

These conditions ensure that the leftist tree is a heap (the element with the minimum key is on the top of the heap), and that the shortest path to a leaf node is obtained by following the rightlink. Donald Knuth called this tree leftist, ``because it tends to ``lean'' so heavily to the left''. So described leftist tree can handle Insert, Merge, and DeleteMin operation in $O( \lg n)$ time. To support delete of an arbitrary element of the tree ( DeleteElement) and preserve the leftist property of the tree pointers to the parent of each node are required. DeleteElement operation also achieves $O( \lg n)$ time complexity.
An alternate way called lazy deletion for implementing deletion of an arbitrary element of the leftist tree was proposed by R. E. Tarjan and D. Cheriton in [CT76]. Their method requires an additional field which shows whether the node is deleted or not. Deletion simply marks the node as deleted, thus requiring constant time. Whenever a DeleteMin or FindMin operation is required, a preorder traversal of the leftist tree is performed as needed, to discover the minimum element. All deleted elements during the traversal are physically deleted and their corresponding subtrees merged. The time complexity of FindMin operation is: $T_{FindMin} = m O(\lg n)$, where m is the number of elements marked as deleted. Information on the lazy delete method can also be found in [Hor84] and [Tar83].

I have chosen to implement a leftist heap with parent pointers. All operations of the leftist tree are expressed using the Merge operation. See Appendix C for pseudo code of the implementation.

Figure 3.10 shows a scenario of insertion of a new node in existing leftist tree. The insertion is implemented by a merge of a one-node leftist tree, H2, with the leftist tree, H1. In this particular case the insertion follows the stack discipline. Figures 3.11 and 3.12 show a merge of two leftist trees. The path of the merge is highlighted in bold.

An improvement of the performance of the merge operation can be achieved by implementing a non-recursive merge. The implementation needs to mimic the runtime stack and remember using additional data structure, the path of the merge, i.e., the points of the leftist tree where potential violation of the rank constraints may occur. After the merge is completed the implementation should follow back the merge path and correct the ranks and swap the left and right subheaps when needed.

  

Figure 3.10: Insertion of a node is a merge of a one-node heap with another heap.

  

Figure 3.11: Two leftist heaps H1 and H2 prior to merging.

  

Figure 3.12: The leftist heap H produced as a result of the Merge.