Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Leftist tree
From Wikipedia, the free encyclopedia
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.
Leftist Trees at Dr. Sartaj Sahni's website (Department Chair in CISE at University of Florida)
