Algorithms for Skew Heap Operations

Skew Heaps are a self-adjusting form of Leftist Heap. By unconditionally swapping all nodes in the right merge path Skew Heaps maintain a short right path from the root.

The following operations can be executed on Skew 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)

Heap dummy;

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

// Swap children of h1
dummy = h1.right;

h1.right = h1.left;

h1.left = dummy;

return h1;