P.rank = 1 + min( (P.left).rank, (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
time. To support delete of an arbitrary element of the
DeleteElement) and preserve the leftist property of the tree
pointers to the parent of each node are required.
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: , 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.