import java.util.*;
import java.io.*;

public class NHeap {

	ArrayList<Integer> myValues;

	public static String nextLine (BufferedReader in) {
		try {
			return (in.readLine ( ));
		} catch (IOException e) {
			return null;
		}
	}
	
	public NHeap (String fileName) {
		myValues = new ArrayList<Integer> ( );
		BufferedReader fileIn = null;
		try {
			FileInputStream dbFileInStream = new FileInputStream (fileName);
			fileIn = new BufferedReader (new InputStreamReader (dbFileInStream));
		} catch (Exception e) {
			System.err.println ("Can't open file " + fileName);
			System.exit (1);
		}
		while (true) {
			String s = nextLine (fileIn);
			if (s == null) {
				break;
			}
			// Equivalent to 
			//	k = Integer.parseInt(s); 
			//	myValues.add (new Integer(k));
			myValues.add (Integer.valueOf(s));
		}
	}
	
	public String toString ( ) {
		String s = "";
		Iterator iter = myValues.iterator ( );
		while (iter.hasNext ( )) {
			s = s + iter.next ( ) + " ";
		}
		return s;
	}
	
	//
	// Check whether the heap object really represents a heap.
	//
	public boolean isOK ( ) {
		for (int k=0; k<myValues.size()/2; k++) {
			int elem = myValues.get(k);
			int child1 = myValues.get(2*k+1);
			int child2 = myValues.get(2*k+2);
			if (elem < child1 || elem < child2) {
				return false;
			}
		}
		return true;
	}
	
	// Insert the given value into the heap, by starting it at the bottom
	// and bubbling it up.
	public void insert (int newValue) {
		myValues.add(new Integer(newValue));
		for (int k=myValues.size()-1; k>1; k = (k-1)/2) {
			int elem = myValues.get(k);
			int parent = myValues.get((k-1)/2);
			// Is the value already in correct place?
			if (elem < parent) {	
				break;
			}
			// No; move it higher in the heap.
			Integer temp = myValues.get(k);
			myValues.set(myValues.get((k-1)/2), k);
			myValues.set(temp, (k-1)/2);
		}
	}

	public static void main (String [ ] args) {
		NHeap heap = new NHeap (args[0]);
		BufferedReader kbdIn = null;
		try {
			kbdIn = new BufferedReader (new InputStreamReader (System.in));
		} catch (Exception e) {
			System.err.println ("Couldn't access keyboard!");
			System.exit (1);
		}
		while (true) {
			if (!heap.isOK ( )) {
				System.out.println ("Not a heap!");
				System.exit (1);
			} else {
				System.out.print ("Element to add to heap = ");
				int value = Integer.parseInt (nextLine(kbdIn));
				heap.insert (value);
				System.out.println ("Heap = " + heap);
			}
		}
	}
}