How to Use a Skew Heap in Java

A skew heap is an abstract data structure. Though Java doesn't provide for a binary tree class, the skew heap can be thought of as a self-organizing binary search tree. The Java Skew Heap class implements the Comparable interface so lists of SkewHeap objects can be sorted easily.

Instructions

1. Write the skeleton of the SkewHeap class. The variables of interest are value (the node's value) and left and right (the left and right children). The tmp and indent static variables are used for temporary space in the merge and print methods. The constructor initializes value and leaves left and right as null.""public class SkewHeap implements Comparable {
int value;
SkewHeap left, right;
static LinkedList tmp;
static int indent = 0; public SkewHeap(int val) {
value = val;
}
}""

2. Use the compareTo method as a way to fulfill the Comparable interface and allow lists of SkewHeap objects to be sorted. The compareTo method should return a negative number, zero or positive number, depending on how the two objects should be sorted. Achieve this by performing a subtraction on the two nodes' values such that nodes with lesser values are sorted before nodes of greater value.""public int compareTo(SkewHeap h) {
return value--h.value;
}""

3. Compose the chop method, an important method used by merge. When a merge is performed, both heaps are chopped apart down the right side. The chop method performs that chop and adds the remaining subheaps to the tmp list.""public void chop() {
SkewHeap r = right;
right = null;

if( r != null ) r.chop();
tmp.addLast(this);
}""

4. Create the merge method. The insert and removeHead methods both use merge to accomplish their task. The merge method will chop both heaps to be merged, which stores all of the subheaps in tmp.

5. Accomplish sorting the tmp linked list and combining the subheaps by removing the last two heaps from the list. Add one as the right child of the other, swap the right and left children and add the heap back to the end of the list. In this way, chopped subheaps are reassembled into a single balanced heap. Left nodes are always guaranteed to be less than the right nodes, and child nodes have a greater value than parent nodes.""public SkewHeap merge(SkewHeap h) {
// Chop the nodes down the right path
tmp = new LinkedList();
chop();
h.chop();

// Sort the nodes
Collections.sort(tmp);

// Merge the subheaps
while(tmp.size() > 1) {
SkewHeap a = tmp.removeLast();
SkewHeap b = tmp.removeLast();

b.right = b.left;
b.left = a;

tmp.addLast(b);
}

return tmp.getFirst();
}""

6. Write the removeHead method. This will remove the head node and merge the left and right child heaps.""public SkewHeap removeHead() {
if( left == null && right == null ) return null;
else if( left == null ) return right;
else if( right == null ) return left;
else return left.merge(right);
}""

7. Formulate the print method. This method is important for debugging, as debuggers don't often have the facilities to view nested data structures like this skew heap. It's recursive and indents correctly.""public void print() {
for( int i = 0; i < indent; ++i ) System.out.print(" ");

System.out.println(value);
indent++;
if( left != null ) {
for( int i = 0; i < indent; ++i ) System.out.print(" ");
System.out.println("<-");
left.print();
}
if( right != null ) {
for( int i = 0; i < indent; ++i ) System.out.print(" ");
System.out.println("->");
right.print();
}
indent--;
}""

Tips & Warnings

• The insert method is a small wrapper around merge to create a single node and merge it with the heap.