import java.util.*;

public class Heap{ //implement an Integer heap using Java ArrayList, 4 methods implemented
    private ArrayList<Integer> al;
    
    public Heap(){
        al=new ArrayList<Integer>();
    }
    
    public Heap(ArrayList<Integer> al){
        this.al=new ArrayList<Integer>(al);
    }
    
     public boolean isEmpty(){
        return al.isEmpty();
    }
    
    public int size(){
        return al.size();
    }
    
    public void insert(Integer obj){//insert at the end and maintain heap properties
        al.add(obj);
        int child=this.size()-1; //each child has only 1 parent
        int parent=(child-1)/2;
        while(parent>=0 && al.get(parent).compareTo(al.get(child))>0){
            Integer temp=al.get(child);
            al.set(child, al.get(parent));
            al.set(parent, temp);
            child=parent;
            parent=(child-1)/2;  //stops at 0.
        }
    }
    
    public Integer delete(){//replace root with end and maintain heap properties
        if(this.isEmpty())
            return null;
        if(this.size()==1)
            return al.remove(0);
        Integer min=al.get(0);
        al.set(0, al.remove(this.size()-1));
        int parent=0; //each parent may have 0, 1, 2 children
        while(true){
            int leftChild=(2*parent)+1;
            int rightChild=leftChild+1;
            if(leftChild>=this.size())
                break;
            int minChild=leftChild;
            if(rightChild<this.size() && al.get(leftChild).compareTo(al.get(rightChild))>0)
                minChild=rightChild;
            if(al.get(parent).compareTo(al.get(minChild))>0){
                Integer temp=al.get(parent);
                al.set(parent, al.get(minChild));
                al.set(minChild, temp);
                parent=minChild;
            }
            else
                break;
        }
        return min;
    }
   
    public void heapSort(){//print all elements in an sorted order. And don't destroy the heap.
        Heap copy=new Heap(this.al);
        System.out.println("\nThe sorted data list is:");
        while(!copy.isEmpty())
            System.out.print(copy.delete()+"\t");
        System.out.println("\n");

    }
}