public class SkewHeap <V extends Comparable<V>> { SkewNode root; public SkewHeap() { this.root = null; } class SkewNode { SkewNode leftChild, rightChild; V data; public SkewNode(V _data, SkewNode _left, SkewNode _right) { this.data = _data; this.leftChild = _left; this.rightChild = _right; } } }
And here the crucial merge:SkewNode merge(SkewNode left, SkewNode right) { if (null == left) return right; if (null == right) return left; if (left.data.compareTo(right.data) < 0 || left.data.compareTo(right.data) == 0) { return new SkewNode(left.data, merge(right, left.rightChild), left.leftChild); } else return new SkewNode(right.data, merge(left, right.rightChild), right.leftChild); }
It's doing exactly what's Wikipedia says: maintains structure and keeping minimum in the root. The others pop and insert use this procedure. Sorting is done via three functions:
SkewHeap listToHeap(List list) { SkewHeap o = new SkewHeap(); for (int i = 0; i < list.size(); i++) o.insert((Comparable) list.get(i)); return o; } List heapToList(SkewHeap tree) { List ll = new ArrayList(); try { while (true) { ll.add(tree.pop()); } } catch (IndexOutOfBoundsException e) { return ll; } } List sort(List list) { return heapToList(listToHeap(list)); }
The first as is seen packs the list parameter to the heap, another stack the whole heap to the list (popping minimums), the resulted list must be sorted than, and finally the sort composes them two. Performance of sorting is O(nlog(n)), though is worse than standard Java sort. Code on github. Thank you.
Sources: Wikipedia , What is Good About Haskell
No comments:
Post a Comment