rendered paste body// ************ heap.java **********************\\package heap;import java.util.ArrayList;import java.lang.Comparable;public class Heap<E> implements PriorityQueue<E>{ private ArrayList<E> tree; private E tmp; public Heap() { this.tree = new ArrayList<E>(); } public boolean isEmpty() { return this.tree.size() == 0; } public boolean add(E obj) { this.tree.add(obj); this.percolateUp(); return true; } public E peek() { return this.tree.get(0); } public E remove() { if (this.isEmpty()) { throw new IndexOutOfBoundsException(); } tmp = this.tree.get(0); if (this.tree.size() == 1) { this.tree.remove(0); } else { this.tree.set(0, this.tree.remove(this.tree.size() - 1)); this.percolateDown(); } return tmp; } public String toString() { return this.tree.toString(); } private int parent(int node) { return (node - 1) / 2; } private int leftChild(int node) { return 2 * node + 1; } private int rightChild(int node) { return 2 * node + 2; } private void percolateUp() { int pos = tree.size() - 1; while (pos > 0) { if (comp(tree.get(pos), tree.get(parent(pos))) < 0) { this.swapNode(pos, parent(pos)); pos = parent(pos); } else break; } } private void percolateDown() { int whereIAm = 0, lesserChild = getLesserChild(0); while (lesserChild != -1) { if (comp(tree.get(whereIAm), tree.get(lesserChild)) > 0) { swapNode(whereIAm, lesserChild); whereIAm = lesserChild; lesserChild = getLesserChild(whereIAm); } else break; } } private int comp(E obj, E other) { return (((Comparable) obj).compareTo((Comparable) other)); } private void swapNode(int beg, int end) { this.tmp = tree.get(beg); tree.set(beg, tree.get(end)); tree.set(end, tmp); } private int getLesserChild(int pos) { if (leftChild(pos) >= tree.size()) return -1; if (rightChild(pos) >= tree.size()) return leftChild(pos); if (comp(tree.get(leftChild(pos)), tree.get(rightChild(pos))) < 0) return leftChild(pos); else return rightChild(pos); } public void drawAsTree() { if (this.isEmpty()) { System.out.println("[empty heap]"); } else { System.out.println(makeSingleString(drawTreeFromNode(0, "none"))); } } private String makeSingleString(ArrayList<String> lines) { String retVal = ""; for (int i = 0; i < lines.size(); i++) { retVal += lines.get(i); if (i < lines.size() - 1) { retVal += "\n"; } } return retVal; } private ArrayList<String> combine(ArrayList<String> left, int leftWidth, ArrayList<String> right, int rightWidth) { int maxSize = (left.size() > right.size()) ? left.size() : right.size(); ArrayList<String> retVal = new ArrayList<String>(maxSize + 1); if (maxSize > 0) { retVal.add(copies(" ", leftWidth) + "|" + copies(" ", rightWidth)); } for (int i = 0; i < maxSize; i++) { String leftSide = (i < left.size()) ? left.get(i) : copies(" ", leftWidth); String rightSide = (i < right.size()) ? right.get(i) : copies(" ", rightWidth); if (leftSide.length() < leftWidth) { leftSide = copies(" ", leftWidth - leftSide.length()) + leftSide; } if (rightSide.length() < rightWidth) { rightSide = rightSide + copies(" ", rightWidth - rightSide.length()); } String joinChar = (i == 0) ? "+" : " "; retVal.add(leftSide + joinChar + rightSide); } return retVal; } private int maxLength(ArrayList<String> lines) { int maxLength = 0;for (String line : lines) { if (line.length() > maxLength) { maxLength = line.length(); } } return maxLength; } private String copies(String val, int num) { String retVal = ""; for (int i = 0; i < num; i++) { retVal += val; } return retVal; } private ArrayList<String> drawTreeFromNode(int nodeNum, String branch) { if (nodeNum >= this.tree.size()) { return new ArrayList<String>(); } else { String val = "" + this.tree.get(nodeNum); ArrayList<String> lines = new ArrayList<String>(); ArrayList<String> leftSubTree = drawTreeFromNode(leftChild(nodeNum), "left"); int leftWidth = Math.max(val.length() / 2, maxLength(leftSubTree)); ArrayList<String> rightSubTree = drawTreeFromNode(rightChild(nodeNum), "right"); int rightWidth = Math.max((val.length() - 1) / 2, maxLength(rightSubTree)); if (branch.equals("left")) { lines.add(copies(" ", leftWidth) + "+" + copies("-", rightWidth)); lines.add(copies(" ", leftWidth) + "|" + copies(" ", rightWidth)); } else if (branch.equals("right")) { lines.add(copies("-", leftWidth) + "+" + copies(" ", rightWidth)); lines.add(copies(" ", leftWidth) + "|" + copies(" ", rightWidth)); } lines.add(copies(" ", leftWidth - val.length() / 2) + val + copies(" ", rightWidth - (val.length() - val.length() / 2 - 1))); ArrayList<String> subTree = combine(leftSubTree, leftWidth, rightSubTree, rightWidth);for (String line : subTree) { lines.add(line); } return lines; } }}// ************* HeapTest.java **************** \\ package heap;import java.util.ArrayList;import java.util.Random;/** * The test class HeapTest. * * @author Todd O'Bryan * @version January 2006 */public class HeapTest extends junit.framework.TestCase { private Heap<Integer> h; protected void setUp() { h = new Heap<Integer>(); } public void testEmptyHeap() { assertEquals("[]", h.toString()); } public void testInsertSingleElement() { h.add(1); assertEquals("[1]", h.toString()); } public void testInsertSeveralNoPercUp() { h.add(1); h.add(2); h.add(3); h.add(4); h.add(5); assertEquals("[1, 2, 3, 4, 5]", h.toString()); } public void testInsertOnePercUp() { h.add(2); h.add(1); assertEquals("[1, 2]", h.toString()); } public void testPercAllTheWay() { for (int i = 1; i <= 10; i++) { h.add(i); } h.add(0); assertEquals("[0, 1, 3, 4, 2, 6, 7, 8, 9, 10, 5]", h.toString()); } public void testPercPartWay() { for (int i = 0; i <= 18; i += 2) { h.add(i); } h.add(1); assertEquals("[0, 1, 4, 6, 2, 10, 12, 14, 16, 18, 8]", h.toString()); } public void testPercDownSingleElement() { h.add(1); h.add(2); h.remove(); assertEquals("[2]", h.toString()); } public void testPercDownTwoElements() { h.add(1); h.add(2); h.add(3); h.remove(); assertEquals("[2, 3]", h.toString()); } public void testPercRight() { h.add(3); h.add(7); h.add(5); h.add(10); h.remove(); assertEquals("[5, 7, 10]", h.toString()); } public void testPercAllTheWayLeft() { for (int i = 1; i <= 17; i++) { h.add(i); } h.remove(); assertEquals("[2, 4, 3, 8, 5, 6, 7, 16, 9, 10, 11, 12, 13, 14, 15, 17]", h.toString()); } public void testPercAllTheWayRight() { h.add(1); h.add(3); h.add(2); h.add(7); h.add(6); h.add(5); h.add(4); for (int i=15; i>=8; i--) { h.add(i); } h.add(16); h.remove(); assertEquals("[2, 3, 4, 7, 6, 5, 8, 15, 14, 13, 12, 11, 10, 9, 16]", h.toString()); } public void testPercBackAndForth() { h.add(1); h.add(2); h.add(3); h.add(5); h.add(4); h.add(10); h.add(11); h.add(8); h.add(9); h.add(6); h.add(10); h.add(50); h.remove(); assertEquals("[2, 4, 3, 5, 6, 10, 11, 8, 9, 50, 10]", h.toString()); } public void testHeapSort10() { Random rand = new Random(); for (int i = 0; i < 10; i++) { h.add(rand.nextInt(100)); } Integer lastMin = h.remove(); Integer thisMin; for (int i = 0; i < 9; i++) { thisMin = h.remove(); assertTrue(lastMin.compareTo(thisMin) <= 0); lastMin = thisMin; } } public void testHeapSort100() { Random rand = new Random(); for (int i = 0; i < 100; i++) { h.add(rand.nextInt(1000)); } Integer lastMin = h.remove(); Integer thisMin; for (int i = 0; i < 99; i++) { thisMin = h.remove(); assertTrue(lastMin.compareTo(thisMin) <= 0); lastMin = thisMin; } } public void testHeapSort1000() { Random rand = new Random(); for (int i = 0; i < 100; i++) { h.add(rand.nextInt(1000)); } Integer lastMin = h.remove(); Integer thisMin; for (int i = 0; i < 99; i++) { thisMin = h.remove(); assertTrue(lastMin.compareTo(thisMin) <= 0); lastMin = thisMin; } } }// ******** PriorityQueue.java ******** \\package heap;public interface PriorityQueue<E> { boolean add(E obj); boolean isEmpty(); E remove(); E peek();}