import java.util.*;

public class MinHeap { 

	// array to hold data values for the minheap, level by level
	// do not use index 0 of the array
	// heap is stored in positions 1 to numElements in the array
	private int[] data;
	private int numElements;

	public MinHeap() { 
		data = new int[1001];	// Heap can hold up to 1000 ints
		numElements = 0;
	}

	/**
	 * Inserts the item into the minheap if there is room.
	 * Otherwise the heap does not change.
	 * @param item Element to be inserted into the minheap.
	 */
	public void insert(int item) { 
		if (numElements == 1000)
			return;
		numElements++;
		data[numElements] = item;
		fixHeapUp();
	}

	private void fixHeapUp() {
		int i = numElements;   // i = index of inserted element
		while (i > 0 && data[i] < data[i/2])
		{ 
			swap(i, i/2); 
			i = i/2; 
		}
	} 

	public int remove() { 
		if (numElements == 0)
			throw new NoSuchElementException();
		int min = data[1]; 
		data[1] = data[numElements];
		numElements--;
		fixHeapDown(); 
		return min;
	} 

	private void fixHeapDown() { 
		int i = 1; // i is index of moved element
		while (i*2 <= numElements) {
			int j = i*2;	// j is index of smaller child
					// assume left child is smaller first
			if (j+1 <= numElements && data[j+1] < data[j])
				j++;	// right is smaller instead
			if (data[i] <= data[j])
				return;		// heap is now fixed
			swap(i, j);
			i = j;		// moved element is now in child's position

		}
	}

	private void swap(int j, int k) { 
		// Swap items of heap at indices j and k 
		int temp = data[j]; 
		data[j] = data[k];
		data[k] = temp;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= numElements; i++) 
			sb.append(data[i] + " ");
		sb.append(" (numElements = " + numElements + ")");
		return sb.toString();
	}		

}