Leftist tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a leftist tree or leftist heap is a <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a> implemented with a variant of a <a href="/facts/Binary_heap/YPJAEN94">binary heap</a>. Every node x has an s-value which is the distance to the nearest <a href="/facts/Leaf_node/RcXz9noF">leaf</a> in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the <a href="/facts/Heap_(data_structure)/A67B0K7L">heap</a> 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 <a href="/facts/Mergeable_heap/GQsK1Gp3">mergeable heap</a>. 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 <a href="/facts/Fibonacci_heap/4cJIHkNQ">Fibonacci heaps</a>, which support insertion in O(1) (constant) <a href="/facts/Amortized/9fFYenJz">amortized</a> 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 <a href="/facts/Skew_heap/hcX8HErL">skew heaps</a> 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.

Leftist tree open-in-new

Leftist tree