// HeapExample.java

class IntHeap {
    private int[] array;
    private int count;

    // start with nothing
    public IntHeap(int size) {
        array = new int[size];
        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(int item) {
        // put item in next available slot
        array[count] = item;

        // keep indices into node we inserted and its parent
        int node = count;
        int p = parent(node);

        // increment total number of items
        count++;

        // upheap until it's root, or parent is bigger
        while ((node != 0) && (array[node] > array[p])) {
            // swap values
            int temp = array[node];
            array[node] = array[p];
            array[p] = temp;

            // update indices
            node = p;
            p = parent(node);
        }
    }


    // remove the top item
    public int dequeue() {
        // set aside root
        int retValue = array[0];

        // move last value to the root
        array[0] = array[count - 1];
        count--;

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

        // while one child is bigger than us
        while ((l < count) && (array[l] > array[node]) ||
               (r < count) && (array[r] > array[node])) {

            // find biggest child
            int max;
            if (l < count && r < count) {
                if (array[l] > array[r]) {
                    max = l;
                } else {
                    max = r;
                }
            } else {
                max = l;
            }

            // swap with the biggest child
            int temp = array[node];
            array[node] = array[max];
            array[max] = temp;

            // update indices
            node = max;
            l = left(node);
            r = right(node);
        }
        
        // return orig. root
        return retValue;
    }

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

    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] + " ");
        }

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


public class HeapExample {
    public static void main(String args[]) {
        // make a heap of up to 100 numbers
        IntHeap heap = new IntHeap(100);

        int[] nums = {32, 64, 99, 28, 6, 42, 54, 7, 19};
        for (int i = 0; i < 9; i++) {
            heap.insert(nums[i]);
        }

        // dequeue them all
        while (heap.getCount() > 0) {
            System.out.println(heap.dequeue());
        }
    }
}