/* Heap als Implementierung einer Priority Queue  */

class Heap implements PriorityQueue {
	private HeapNode[] heap; // Array to store the heap elements
	private int size;  // position of last insertion into the heap

	/**
	 * Construct the binary heap.
	 * @param size how many items the heap can store
	 */
	Heap(int size) {
		// Array für 'size' HeapNodes anlegen
		// heap[0] is reserved for the dummy element
	}

	/**
	 * Returns the number of elements in this priority queue.
	 * @return the number of elements in this priority queue.
	 */	
	public int size(){
		// TODO implement method size
	}
	
	/**
	 * Check whether the heap is empty.
	 * @return true if there are no items in the heap.
	 */
	public boolean isEmpty() {
		// TODO implement method isEmpty
	}
	
	/**
	 * Check whether the heap is full.
	 * @return true if no further elements can be inserted into the heap.
	 */
	public boolean isFull() {
		// TODO implement method isFull
	}

	/**
	 * Make the heap (logically) empty.
	 */	
	public void clear() {
		// TODO implement method clear
	}

	/**
	 * Insert into the priority queue, maintaining heap order.
	 * Duplicates are allowed.
	 * @param obj the item to insert
	 * @param priority the priority to be assigned to the item obj
	 * @exception Overflow if the heap is full
	 */
	public void insert(Object obj, long priority) throws QueueFullException {
		// TODO implement method insert
	}

	/**
	 * Delete the smallest item from the priority queue, maintaining heap order.
	 * @return the the smallest item, or null, if empty
	 */
	public Object deleteMin() throws QueueEmptyException {
		// TODO implement method deleteMin
	}
	
	/**
	 * Internal method to percolate down in the heap.
	 * @param start the index at which the percolate begins
	 */
	private void percolateDown(int start) {	
	}

	public long[] toLongArray() {
	// gibt alle Prioritaeten als array zurück. An der Position 0
	// soll die hoechste Prioritaet (kleinster Wert) stehen, das
	// dummy Element soll nicht berücksichtigt werden.
		// TODO implement method toLongArray
	}
}

class HeapNode {
	Object obj;
	long priority;
	
	HeapNode( Object obj, long priority) {
		this.obj = obj;
		this.priority = priority;
	}
}