PQHeap.java

import java.util.Arrays.*;

public class PQHeap implements PQ {
    private Element[] heap;
    private int heapSize;
    private int maxElems;

    public PQHeap(int maxElems) {
        this.heap     = new Element[maxElems];
        this.heapSize = 0;
        this.maxElems = maxElems;
    }

    public void insert(Element e) {
        // Double size of heap if we've reached the end
        // Creating a new array and copying is required.
        if(this.heapSize == this.maxElems) {
            this.maxElems *= 2;
            Element[] newHeap = new Element[maxElems];
            for(int i = 0; i < this.heapSize; i++) {
                newHeap[i] = this.heap[i];
            }
            this.heap = newHeap;
        }

        this.heapSize++;
        // This element needs to have a lower priority(bigger key)
        // than the element we are inserting.
        this.heap[this.heapSize - 1] = new Element(
                e.key + 1,
                e.key + 1);
        this.decreaseKey(this.heapSize - 1, e);
    }

    public boolean hasElements() {
        return this.heapSize > 0;
    }

    public int getSize() {
        return this.heapSize;
    }

    /**
     * Extract highest priority element(root node) and minHeapify
     * to put new highest priority element at root node.
     **/
    public Element extractMin() {
        if(this.heapSize < 1) {
            throw new IllegalStateException("Heap underflow");
        }
        Element min  = this.heap[0];
        this.heap[0] = this.heap[this.heapSize - 1];
        this.heapSize--;
        this.minHeapify(0);
        return min;
    }

    /**
     * Construct min heap out of unordered array of elements.
     * Current heap gets replaced by new heap.
     **/
    public void buildMinHeap(Element[] elements) {
        this.heap     = elements;
        this.heapSize = elements.length;
        for(int i = this.heapSize / 2 - 1; i >= 0; i--) {
            this.minHeapify(i);
        }
    }

    /**
     * Utility functions for parent/left child/right child
     * accounting for 0-indexing.
     **/
    private int parent(int i) { return (i - 1) >> 1; }
    private int left(int i)   { return (i << 1) + 1; }
    private int right(int i)  { return (i << 1) + 2; }

    /**
     * decreaseKey as per the book on page 164's increaseKey
     * modified for a min heap instead of a max heap.
     **/
    private void decreaseKey(int i, Element e) {
        if (e.key > this.heap[i].key) {
            throw new IllegalArgumentException("Bad key");
        }
        // Insert the element into the heap at the given position
        // and swap it up the tree as long as it has higher priority(lower
        // key) than its parent.
        this.heap[i] = e;
        while (i > 0 && this.heap[parent(i)].key > this.heap[i].key) {
            Element temp = this.heap[i];
            this.heap[i] = this.heap[parent(i)];
            this.heap[parent(i)] = temp;
            i = parent(i);
        }
    }

    /**
     * minHeapify as per page 154's maxHeapify, modified for a min heap.
     * Ensures the min heap property is satisfied by swapping elements
     * with their children if they have higher priority(lower key).
     **/
    private void minHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;

        // Determine the element with highest priority out of the element
        // itself and its children.
        if (l < this.heapSize && this.heap[l].key < this.heap[i].key) {
            smallest = l;
        }

        if (r < this.heapSize && this.heap[r].key < this.heap[smallest].key) {
            smallest = r;
        }

        // If the element itself doesn't have higher priority than its
        // children, swap it with the highest priority child.
        if (smallest != i) {
            Element temp = this.heap[i];
            this.heap[i] = this.heap[smallest];
            this.heap[smallest] = temp;
            this.minHeapify(smallest);
        }
    }
}