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. Union (Heap h1, Heap h2)

Note that the operation Union is used for Inserts and DeleteMin as specified below.

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 = Union (h.left, h.right);

return e;

Insert (Heap h, Element e)

z = MakeHeap(e);

h = Union (h, z);

Union (Heap h1, heap h2)

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 = Union (h1.right, h2);

// 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;