// MinHeap.java

public class MinHeap<Type> {
    private class Element {
        public Type value;
        public double priority;
        
        public Element(Type v, double p) {
            value = v;
            priority = p;
        }
    }
    
    private Element[] array;
    private int count;

    // start with nothing
    public MinHeap(int size) {
        // make the array which requires a 
        @SuppressWarnings("unchecked")
        Element[] arr = (Element[]) new MinHeap.Element[size];
        array = arr;
        count = 0;
    }

    // find the left child of a node
    public int left(int node) {
        return 2 * node  + 1;
    }

    // find the right child of a node
    public int right(int node) {
        return 2 * node  + 2; 
    }

    // find the parent of a node
    public int parent(int node) {
        return (node - 1) / 2;
    }

    // insert an item into the heap
    public void insert(Type value, double priority) {
        // put the new one in the next slot
        array[count] = new Element(value, priority);
        int node = count;
        int p = parent(node);
        count++;

        // upheap it until it is under a node which is bigger than it (or the root)
        while ((node != 0) && (array[node].priority < array[p].priority)) {
            Element temp = array[node];
            array[node] = array[p];
            array[p] = temp;

            node = p;
            p = parent(node);
        }
    }


    // remove the top item
    public Type dequeue() {
        // save the item to return it
        Element element = array[0];

        // move the last item to the root and decrement
        array[0] = array[count - 1];
        count--;

        // find the children
        int node = 0;
        int l = left(node);
        int r = right(node);

        // while one of the children is bigger - or equal
        while (((l < count) && (array[l].priority < array[node].priority)) ||
                ((r < count) && (array[r].priority < array[node].priority))) {

            // find the larger node
            int max;

            // if there are two, take smaller
            if ((l < count) && (r < count)) {
                if (array[l].priority < array[r].priority)
                    max = l;
                else
                    max = r;
            }
            // if just one take that one
            else if (l < count) {
                max = l;
            } else {
                max = r;
            }

            // swap them
            Element temp = array[max];
            array[max] = array[node];
            array[node] = temp;

            node = max;
            l = left(node);
            r = right(node);
        }

        return element.value;
    }

    // return the largest item in the heap
    public Type max() {
        return array[0].value;
    }

    public int getCount() {
        return count;
    }

    // print the contents of the array
    public void print() {
        System.out.print("Heap: ");
        for (int i = 0; i < count; i++) {
            System.out.print(array[i].value + " ");
        }

        System.out.print("\n");
    }
}