In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value. The height-biased leftist tree was invented by Clark Allan Crane. The name comes from the fact that the left subtree is usually taller than the right subtree. A leftist tree is a mergeable heap. When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete an item, it is replaced by the merge of its left and right sub-trees. Both these operations take O(log n) time. For insertions, this is slower than Fibonacci heaps, which support insertion in O(1) (constant) amortized time, and O(log n) worst-case. Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, the merging of skew heaps has better performance. However merging leftist heaps has worst-case O(log n) complexity while merging skew heaps has only amortized O(log n) complexity.
Bias The usual leftist tree is a height-biased leftist tree. However, other biases can exist, such as in the weight-biased leftist tree. The exact worst-case complexity of both types of leftist trees is 2 log2 n, counting comparisons. The exact amortized complexity of weight-biased leftist trees is known to match the logφ n (approximately 1.44 log2 n) exact amortized complexity of skew heaps, where φ denotes the golden ratio; similarly, the amortized complexity of height-biased leftist trees is bounded below by logφ n, but whether this is also the upper bound is an open problem.
S-value
The s-value (or rank) of a node is the distance from that node to the nearest empty position in the subtree rooted at that node. Put another way, the s-value of a null child is implicitly zero. Other nodes have an s-value equal to one more the minimum of their children's s-values. Thus, in the example at right, all nodes with at least one missing child have an s-value of 1, while node 4 has an s-value of 2, since its right child (8) has an s-value of 1. (In some descriptions, the s-value of null children is assumed to be −1.) Knowing the shortest path to the nearest missing leaf in the subtree rooted at x is exactly of s(x), every node at depth s(x)−1 or less has exactly 2 children since s(x) would have been less if not. Meaning that the size of the tree rooted at x is at least 2 s ( x ) − 1 {\displaystyle 2^{s(x)}-1} . Thus, s(x) is at most log ( m + 1 ) {\displaystyle \log {(m+1)}} , m being the number of nodes of the subtree rooted at x.
Operations on a height biased leftist tree Most operations on a Height Biased Leftist Tree are done using the merge operation.
Merging two Min HBLTs The merge operation takes two Min HBLTs as input and returns a Min HBLT containing all the nodes in the original Min HBLTs put together. If either tree empty, the merged tree is the other. Otherwise, label their roots A and B so that A.key ≤ B.key. To preserve the heap property, A must be the root of the merged tree. The merge is done by recursively merging B with A's right subtree. This may increase the s-value of A's right subtree, and thus A's s-value. If the result has a greater s-value than A's left subtree, swap the two subtrees to maintain the leftist tree property.
Pseudocode for merging two min height biased leftist trees MERGE(A, B) if A = null return B if B = null return A if A.key > B.key return MERGE(B, A) A.right := MERGE (A.right, B) // the result cannot be null since B is non-null if A.left = null then SWAP(A.left, A.right) A.s_value := 1 // since the right subtree is null, the shortest path to a descendant leaf from node A is 1 return A if A.right.s_value > A.left.s_value then SWAP(A.right, A.left) A.s_value := A.right.s_value + 1 return A
Java code for merging two min height biased leftist trees
Haskell code for merging two min height biased leftist trees
Example An example of how the merge operation in a leftist tree works is depicted. The boxes represent each merge call.When the recursion unwinds, we swap left and right children if x.right.s_value > x.left.s_value for every node x. In this case we swapped the subtrees rooted at nodes with keys 7 and 10.
Insertion into a Min HBLT Insertion is done using the merge operation. An insertion of a node into an already existing Min HBLT, creates a HBLT tree of size one with that node and merges it with the existing tree.
INSERT (A, x) B := CREATE_TREE(x) return MERGE(A, B)
Deletion of Min element from Min HBLT The Min element in a Min HBLT is the root. Thus, in order to delete the Min, the root is deleted and its subtrees are merged to form the new Min HBLT.
DELETE_MIN(A) x := A.key A := MERGE (A.right, A.left) return x
Initializing a height biased leftist tree
Initializing a height biased leftist tree is primarily done in one of two ways. The first is to merge each node one at a time into one HBLT. This process is inefficient and takes O(nlogn) time. The other approach is to use a queue to store each node and resulting tree. The first two items in the queue are removed, merged, and placed back into the queue. This can initialize a HBLT in O(n) time. This approach is detailed in the three diagrams supplied. A min height biased leftist tree is shown. To initialize a min HBLT, place each element to be added to the tree into a queue. In the example (see Part 1 to the left), the set of numbers [4, 8, 10, 9, 1, 3, 5, 6, 11] are initialized. Each line of the diagram represents another cycle of the algorithm, depicting the contents of the queue. The first five steps are easy to follow. Notice that the freshly created HBLT is added to the end of the queue. In the fifth step, the first occurrence of an s-value greater than 1 occurs. The sixth step shows two trees merged with each other, with predictable results.
… excerpt ends here. Continue reading the full article.
