Algorithms for Leftist Heap Operations
Leftist tree is a binary tree, heap ordered with the leftist property.
The right merge paths of leftist heaps are swapped based on the dist values of the nodes. This maintains the invariant that the right path of every node has the shortest dist.
Dist[x]: Length of shortest path from x to a descendent external node – 1.
The following operations can be executed on Leftist Heaps:
1. MakeHeap(Element e)
2. FindMin(Heap h)
3. DeleteMin(Heap h)
4. Insert (Heap h, Element e)
5.
Note that the operation
MakeHeap (Element e)
return new Heap(e);
FindMin(Heap h)
if (h == null)
return null;
else
return h.key
DeleteMin(Heap h)
Element e = h.key;
h =
return e;
Insert (Heap h, Element e)
z = MakeHeap(e);
h =
if (h1 == null)
return h2;
else if (h2 == null)
return h1;
else
{
// Assure that the key of h1 is smallest
if (h1.key > h2.key)
{
Node dummy = h1;
h1 = h2;
h2 = dummy;
}
}
if (h1.right == null) // Hook h2 directly to h1
h1.right = h2;
else // Union recursively
h1.right =
// Conditionally swap children of h1
if (h1.left == null || h1.right.dist > h1.left.dist)
{
Node dummy = h1.right;
h1.right = h1.left;
h1.left = dummy;
}
// Update dist values
if (h1.right == null)
h1.dist = 0;
else
h1.dist = h1.right.dist + 1;
return h1;