Leftist tree
A leftist tree or leftist heap is a priority queue implemented with a variant of a binary tree. Leftist trees were invented by Clark Allan Crane and uses the heap structure. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. The two children are sorted such that the right path is the shortest path from the root to an external node. When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete a minimum item, we remove the root and the left and right sub-trees are then melded. Both these operations take O(logn) time. For insertions, this is slower than binary heaps which support insertion in amortized constant time, O(1).
Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, skew heaps have better performance.
S-value
The s-value of a node is the distance between that node and an external (imaginary) node. In the diagram, external nodes are the gray boxes. Note that these external nodes are not actually part of the tree and just serve as a visual aide. The s-value is calculated by counting the least number of movements one must make to move from a node to an external node. In the diagram, the s-value of the top node, 4, is 2 because two movements are necessary to reach an external node. For the other three nodes, the s-value is 1 because only one movement is necessary. All nodes added to a leftist tree start with an s-value of 1. One may also calculate the s-value of a node by looking at the s-value of its children: S(node) = min(S(node.leftChild), S(node.rightChild)) + 1.
Merging height biased leftist trees
To merge two nodes together, first one must decide whether to create a min or max height biased leftist tree. For a min height biased leftist tree, select the node with the lower value (node x) and set the higher value node (node y) as its right child. If a right child already exists, then merge node y with the sub-tree rooted by the right child of node x and repeat the merging process. After merging node x and node y the s-value of node x must be updated (see above section, s-value). Now check if node x has a left child. If it does not, then move the right child to the left. If it does have a left child, then the child with the highest s-value should go on the left.
Java code for merging a min height biased leftist tree
public Node merge(Node x, Node y) {
if(x == null)
return y;
if(y == null)
return x;
// if this was a max height biased leftist tree, then the
// next line would be: if(x.element < y.element)
if(x.element.compareTo(y.element) > 0) {
// x.element > y.element
Node temp = x;
x = y;
y = temp;
}
x.rightChild = merge(x.rightChild, y);
if(x.leftChild == null) {
// left child doesn't exist, so move right child to the left side
x.leftChild = x.rightChild;
x.rightChild = null;
x.s = 1;
} else {
// left child does exist, so compare s-values
if(x.leftChild.s < x.rightChild.s) {
Node temp = x.leftChild;
x.leftChild = x.rightChild;
x.rightChild = temp;
}
// since we know the right child has the lower s-value, we can just
// add one to its s-value
x.s = x.rightChild.s + 1;
}
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.
In part 2 a slightly more complex merge happens. The tree with the lower value (tree x) has a right child, so merge must be called again on the subtree rooted by tree x's right child and the other tree. After the merge with the subtree, the resulting tree is put back into tree x. The s-value of the right child (s=2) is now greater than the s-value of the left child (s=1), so they must be swapped. The s-value of the root node 4 is also now 2.
Part 3 is the most complex. Here, we recursively call merge twice (each time with the right child 's subtree that is not grayed out). This uses the same process described for part 2.
External links
Leftist Trees at Dr. Sartaj Sahni's website (Department Chair in CISE at University of Florida)