Heap.java

/* * Heap.java * * Computer Science S-22, Harvard University */ import java.util.*; /** * Heap - a generic collection class that implements  * a max-at-top heap using an array */public class Heap<T extends Comparable<T>> {    private T[] contents;    private int numItems;        public Heap(int maxSize) {        contents = (T[])new Comparable[maxSize];        numItems = 0;    }        public Heap(T[] arr) {        // Note that we don't copy the array, so that heapsort can        // sort the array in place.        contents = arr;        numItems = arr.length;        makeHeap();    }        /*      * makeHeap - turn the elements in the contents array into a     * representation of a max-at-top heap.     */    private void makeHeap() {        int last = contents.length - 1;        int parentOfLast = (last - 1)/2;        for (int i = parentOfLast; i >= 0; i--)            siftDown(i);    }        /**      * insert - add the specified item to the heap and sift it up     * into its proper position.     */    public void insert(T item) {        if (numItems == contents.length) {            // grow the array            T[] newContents = (T[])new Comparable[contents.length * 2];            System.arraycopy(contents, 0, newContents, 0, numItems);            contents = newContents;        }                contents[numItems] = item;        siftUp(numItems);        numItems++;    }        /**     * remove and return the item at the top of the heap, and adjust     * the remaining items so that we still have a heap.     */    public T remove() {        if (numItems == 0) {            throw new NoSuchElementException();        }                T toRemove = contents[0];                // Move the element currently the end of the heap to the top        // and sift it into place.        contents[0] = contents[numItems - 1];        contents[numItems - 1] = null;        numItems--;        siftDown(0);                return toRemove;    }        /**     * isEmpty - does the heap currently have no items?     */    public boolean isEmpty() {        return (numItems == 0);    }        /**     * toString - create a string representation of the heap of the form     * { ( root ) ( items in level 1 ) ( items in level 2 ) ... }     */    public String toString() {        String str = "{ ";                int start = 0;        int levelSize = 1;        while (start < numItems) {            // print all of the items at the current level of the tree            str += "( ";            for (int i = start; i < start + levelSize && i < numItems; i++)                str += (contents[i] + " ");            str += ") ";                        // move down to the next level            start += levelSize;            levelSize *= 2;        }                str += "}";        return str;    }        /*     * siftDown - sift the element in contents[i] down into its     * correct position in the heap.     */    private void siftDown(int i) {        // Store a reference to the element being sifted.        T toSift = contents[i];                // Find where the sifted element belongs.        int parent = i;        int child = 2 * parent + 1;        while (child < numItems) {            // If the right child is bigger, compare with it.            if (child < numItems - 1  &&                contents[child].compareTo(contents[child + 1]) < 0)                child = child + 1;                        // Check if we're done.            if (toSift.compareTo(contents[child]) >= 0)                break;                        // If not, move child up and move down one level in the tree.            contents[parent] = contents[child];            parent = child;            child = 2 * parent + 1;        }                contents[parent] = toSift;    }        /*     * siftUp - sift the element in contents[i] up into its     * correct position in the heap.     */    private void siftUp(int i) {        // Store a reference to the element being sifted.        T toSift = contents[i];                // Find where the sifted element belongs.        int child = i;        while (child > 0) {            int parent = (child - 1)/2;                        // Check if we're done.            if (toSift.compareTo(contents[parent]) <= 0)                break;                        // If not, move parent down and move up one level in the tree.            contents[child] = contents[parent];            child = parent;        }                contents[child] = toSift;    }        public static void main(String[] args) {        String commandString = "";        Scanner in = new Scanner(System.in);                System.out.print("max size: ");        int maxSize = in.nextInt();        in.nextLine();    // consume the rest of the line        Heap<Integer> heap = new Heap<Integer>(maxSize);                while(true) {            System.out.println(heap);            System.out.println();                        do {                System.out.print("[I]nsert int | [R]emove | [Q]uit : ");                commandString = in.nextLine();            } while (commandString.length() == 0);                         Scanner command = new Scanner(commandString);            String commandChar = command.next();                        try {                if (commandChar.equalsIgnoreCase("q"))                    System.exit(1);                else if (commandChar.equalsIgnoreCase("i")) {                    // insert                    int item = command.nextInt();                    heap.insert(item);                } else if (commandChar.equalsIgnoreCase("r")) {                    // remove (and isEmpty)                    if (heap.isEmpty())                        System.out.println("Heap is empty.");                    else                         System.out.println("Removed: " + heap.remove());                } else                    System.out.println("Invalid command: " + commandString);            } catch (NoSuchElementException e) {                System.out.println("Invalid command: " + commandString);            }        }    }}