In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. 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 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.
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 merged. Both these operations take O(log n) time. For insertions, this is slower than binary heaps which support insertion in amortized constant time, O(1) 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, skew heaps have better performance.
Read more about Leftist Tree: Bias, S-value, Merging Height Biased Leftist Trees, Initializing A Height Biased Leftist Tree
Famous quotes containing the word tree:
“The spring is here, young and beautiful as ever, and absolutely shocking in its display of reckless maternity; but the Judas tree will bloom for you on the Bosphorus if you get there in time. No one ever loved the dog-wood and Judas tree as I have done, and it is my one crown of life to be sure that I am going to take them with me to heaven to enjoy real happiness with the Virgin and them.”
—Henry Brooks Adams (1838–1918)