import java.util.ArrayList;
import java.util.NoSuchElementException;

public class MyMinHeap<E extends Comparable<? super E>>  {
    private ArrayList<E> values;

    public MyMinHeap() {
        this.values = new ArrayList<E>();
    }
    
    public E minValue() {
        if (this.values.size() == 0) {
            throw new NoSuchElementException();
        }
        return this.values.get(0);
    }
    
    public void add(E newValue) {
        values.add(newValue);
        int pos = this.values.size()-1;
        
        while (pos > 0) {
            if (newValue.compareTo(this.values.get((pos-1)/2)) < 0) {
                values.set(pos, this.values.get((pos-1)/2));
                pos = (pos-1)/2;
            }
            else {
                break;
            }
        }
        this.values.set(pos, newValue);
    }
    
    public void remove() {
       E newValue = this.values.remove(this.values.size()-1);
       int pos = 0;
       
       if (this.values.size() > 0) {
           while (2*pos+1 < this.values.size()) {
               int minChild = 2*pos+1;
               if (2*pos+2 < this.values.size() &&
                     this.values.get(2*pos+2).compareTo(this.values.get(2*pos+1)) < 0) {
                   minChild = 2*pos+2;
               }
           
               if (newValue.compareTo(this.values.get(minChild)) > 0) {
                   this.values.set(pos, this.values.get(minChild));
                   pos = minChild;
               }
               else {
                   break;
               }
           }
           this.values.set(pos, newValue);
       }      
   }
    
    public String toString() {
        return values.toString();
    }
    
    public static void main(String[] args) {
        int[] items = {5, 3, 7, 6, 1, 4, 2, 8};

        MyMinHeap<Integer> itemHeap = new MyMinHeap<Integer>();
        for (int i = 0; i < items.length; i++) {
            itemHeap.add(items[i]);
        }

        for (int i = 0; i < items.length; i++) {
            items[i] = itemHeap.minValue();
            itemHeap.remove();
        }

        for (int i : items) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}