import structure5.*; /** * A binary heap implemented as an implicit binary tree on * top of the structure5.Vector class. */ class VectorHeap> { protected Vector data; /** * Returns a new VectorHeap. */ public VectorHeap() { data = new Vector(); } /** * Compute the location of the child to the left of i. * * @param i The index of a subtree root. * @return A location. */ protected static int left(int i) { return 2 * i + 1; } /** * Compute the location of the child to the right of i. * * @param i The index of a subtree root. * @return A location. */ protected static int right(int i) { return 2 * i + 2; } /** * Computer the location of the parent of i. * * @param i The index of a subtree root. * @return A location. */ protected static int parent(int i) { return (i - 1) / 2; } /** * Returns the max element. * * @return An element. */ public E findMax() { if (data.size() == 0) return null; return data.get(0); } /** * Extract the max element, heapify, then return the max. * * @return The max element. */ public E extract() { if (data.size() == 0) return null; E max = data.get(0); data.set(0, data.get(data.size() - 1)); data.remove(); heapDown(0); return max; } /** * Insert an element, then heapify. * * @param value The value to insert. */ public void insert(E value) { data.add(value); heapUp(data.size() - 1); } /** * Returns true iff there are no elements in the tree. * * @return True if empty. */ public boolean isEmpty() { return data.size() == 0; } /** * Compare the given leaf with its parent and swap up recursively * until no more swaps remain. Ensures that the max heap * property is maintained. * * @param leaf The index of a leaf. */ public void heapUp(int leaf) { if (leaf > 0) { int parentIdx = parent(leaf); E value = data.get(leaf); if (value.compareTo(data.get(parentIdx)) > 0) { data.set(leaf, data.get(parentIdx)); data.set(parentIdx, value); heapUp(parentIdx); } } } /** * Compare the given root with its children and swap down recursively * until no more swaps remain. Ensures that the max heap * property is maintained. * * @param root */ public void heapDown(int root) { int leftIdx = left(root); // if there is no left child, there are // no children, so do nothing if (leftIdx < data.size() - 1) { E value = data.get(root); // there is a left child E leftVal = data.get(leftIdx); int rightIdx = right(root); if (rightIdx < data.size()) { // there is also a right child E rightVal = data.get(rightIdx); // since there are two children, we need to find // the larger of the children and compare // against that one if (rightVal.compareTo(leftVal) > 0) { // right is the bigger of the children // is right larger than the root? if so, swap if (rightVal.compareTo(value) > 0) { data.set(rightIdx, value); data.set(root, rightVal); heapDown(rightIdx); return; } } } // there is only a left child // is root smaller than left? if (leftVal.compareTo(value) < 0) { data.set(leftIdx, value); data.set(root, leftVal); heapDown(leftIdx); } } } /** * A simple visualization of our heap. */ public String toString() { return ""; } /** * Some test code. * * @param args Ignored. */ public static void main(String[] args) { VectorHeap v = new VectorHeap<>(); v.insert(56); v.insert(5); v.insert(57); v.insert(0); v.insert(-7); v.insert(99); // what does our heap look like? System.out.println(v); // let's remove some elements System.out.println("Removing: " + v.extract()); System.out.println("Removing: " + v.extract()); // now what does it look like? System.out.println(v); // what's the max now? System.out.println(v.findMax()); } }