public class Item {
    private static int count = 1; 
    private int id;
    private int priority;

    public Item(int thepriority) {
	id = count;
	count++;
	priority = thepriority;
    }

    public int getPriority() {
	return priority;
    }

    public int getId() {
	return id;
    }
}

public class PriorityHeap {
    private final int capacity = 128;
    private Item [] items = new Item[capacity]; 
    private int length;
    
    public PriorityHeap() {
	// do nothing
    }

    public boolean isEmpty() {
	return (length == 0);
    }

    public void enqueue(int priority) { 
	if (length >= capacity) {
	    System.out.println("Queue overflow");
	    System.exit(0);
	}
	Item newItem = new Item(priority);
	items[length] = newItem;
	int k = length;
	int i = parent(k);
	while (i >= 0 && items[k].getPriority() > items[i].getPriority()) {
	    Item temp = items[k];
	    items[k] = items[i];
	    items[i] = temp;
	    k = i;
	    i = parent(i);
	}
	length++;
    }

    public int dequeue() {
	if (length < 1) {
	    System.out.println("Queue underflow");
	    System.exit(0);
	}
	// save away the item to be returned
	Item max = items[0];
	// move the last element to the root of the tree
	items[0] = items[length-1];
	int k = 0;
	int left = 1; // left subtree of the root
	int right = 2; // right subtree of the root

	while (left < length - 1 && right < length - 1 && 
	       (items[k].getPriority() < items[left].getPriority() || 
		items[k].getPriority() < items[right].getPriority()))  {
	    if (items[left].getPriority() >= items[right].getPriority()) {
		Item temp = items[k];
		items[k] = items[left];
		items[left] = temp;
		k = left; 
		right = rightChild(left);
		left = leftChild(left);
	    } else {
		Item temp = items[k];
		items[k] = items[right];
		items[right] = temp;
		k = right;  
		left = leftChild(right);
		right = rightChild(right);
	    }
	}

	// exchanging with the last (incomplete) level elements
	// This is the case when right >= length - 1
	if (left < length - 1 && 
	       items[k].getPriority() < items[left].getPriority()) {
	    Item temp = items[k];
	    items[k] = items[left];
	    items[left] = temp;
	}
	--length;
	return max.getPriority();
    }
    
    public void print() {
	for (int i = 0; i < length; ++i) {
	    System.out.print(" id = " + items[i].getId() + " PRI = " 
			     + items[i].getPriority());
	}
	System.out.println();
    }

    // given an index i, returns the parent of the node 
    // at that index
    // returns -1 for the root
    private int parent(int i) {
	if (i <= 0) return -1;
	return (i - 1)/2;
    }

    // given an index i, returns the left child of the node 
    // at that index
    // doesn't check if the node is within the capacity
    private int leftChild(int i) {
	return i * 2 + 1;
    }

    // given an index i, returns the right child of the node 
    // at that index
    // doesn't check if the node is within the capacity
    private int rightChild(int i) {
	return 2 * (i + 1);
    }    
}

public class TestPriorityHeap {
    public static void main(String [] args) {
	PriorityHeap ph = new PriorityHeap();
	ph.enqueue(3);
	ph.enqueue(4);
	ph.enqueue(2);
	ph.enqueue(4);
	ph.enqueue(5);
	ph.print();
	Item fromqueue = ph.dequeue();
	ph.print();
	ph.enqueue(5);
	ph.print();
	// flush the queue
	while (!ph.isEmpty()) {
	    ph.dequeue();
	}
	ph.print();
	// start all over
	ph.enqueue(55);
	ph.enqueue(1);
	fromqueue = ph.dequeue();
	ph.print();
	ph.enqueue(3);
	ph.enqueue(0);
	ph.print();
    }
}