Algorithms for Skew Heap Operations

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:

• MakeHeap(Element e)
• FindMin(Heap h)
• DeleteMin(Heap h)
• Insert (Heap h, Element e)
• 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;