import java.util.ArrayList;
import java.util.Comparator;
public class BinaryHeap<K> extends Heap<K> {
    private Comparator<K> comp;
    public BinaryHeap(){
        this(new DefaultComparator<K>());
    }
    public BinaryHeap(Comparator<K> comp){
        array = new ArrayList<>();
        this.comp = comp;
    }

    private void swap(int i, int j){
        K temp = array.get(i);
        array.set(i,array.get(j));
        array.set(j,temp);
    }
//    private int root(){

//    }
    private int left(int i){
        return 2*i+1;
    }
    private int right(int i){
        return 2*i+2;
    }
    private int parent(int i){
        return (i-1)/2;
    }
    protected boolean hasLeft(int i){
        return left(i) < array.size();
    }
    protected boolean hasRight(int i){
        return right(i) < array.size();
    }
    private void sink(int i){
        while(hasLeft(i)){
            int leftIndex = left(i);
            int smallChildIndex = leftIndex;
            if(hasRight(i)){
                int rightIndex = right(i);
                if(comp.compare(array.get(leftIndex),array.get(rightIndex))>0)
                    smallChildIndex = rightIndex;
            }
            if(comp.compare(array.get(smallChildIndex),array.get(i)) >= 0)
                break;
            swap(i,smallChildIndex);
            i = smallChildIndex;
        }
    }
    private void swim(int i){
        while(i > 0){
            int p = parent(i);
            if(comp.compare(array.get(i),array.get(p)) >= 0) break;
            swap(i,p);
            i = p;
        }
    }

    public void insert(K k){
        array.add(k);
        swim(array.size()-1);
    }

    public K removeMin(){
        if(array.isEmpty()) return null;
        K answer = array.get(0);
        swap(0,array.size() - 1);
        array.remove(array.size()-1);
        sink(0);
        return answer;
    }
    public K min(){
        if(array.isEmpty()) return null;
        return array.get(0);
    }

    public String toString(){
        String result = new String();
        for (int i = 0; i < array.size(); i++){
            result = result + array.get(i).toString() + " ";
        }
        return result;
    }

    public static void main(String[] args){
        BinaryHeap test = new BinaryHeap();
        test.insert(5);
        test.insert(7);
        test.insert(6);
        test.insert(9);
        test.insert(3);
        test.insert(8);
        test.insert(2);
        test.insert(1);
        test.insert(4);
        System.out.println(test.toString());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
        System.out.println(test.removeMin());
    }
}