import java.util.ArrayList;
import java.util.List;

/**
 * Created by 刘逗逼 on 2016/3/11.
 */
public class MaxHeap<T extends Comparable<T>> {
    private List<T> head;
    public MaxHeap(){
        this.head=new ArrayList<T>();
    }
    protected void filterup(int start){          //向上调整，用于插入
        int child=start;
        int parent=(child-1)/2;                 //因为数组下标从0开始
        T tmp=head.get(child);
        while(true){
            int cmp=head.get(parent).compareTo(tmp);
            if(cmp>0){
                break;
            }else {             //换位
                head.set(child,head.get(parent));
                child=parent;
                parent=(parent-1)/2;
            }
        }
        head.set(child,tmp);
    }
    protected void filterdown(int start,int end){       //end是判断是否出界的
        int parent=start;
        int left=2*parent+1;
        T tmp=head.get(parent);
        while(left<=end){
            int cmp=head.get(left).compareTo(head.get(left+1));
            if(cmp<0)left=+1;
            head.set(parent,head.get(left));
            cmp=head.get(parent).compareTo(head.get(left));
            if(cmp>0){
                break;
            }else {
                head.set(parent,head.get(left));
                parent=left;
                left=left*2+1;
            }
        }
        head.set(parent,tmp);
    }
      /*
       * 删除最大堆中的data
       *
       * 返回值：
       *      0，成功
       *     -1，失败
       */

    protected int remove(T data){
        if(head.isEmpty()){
            return -1;
        }
        int index=head.indexOf(data);
        if(index==-1)return -1;
        int size=head.size();
        head.set(index,head.get(size-1));
        head.remove(size-1);
        if(head.size()>1){
            filterdown(index,head.size()-1);
        }
        return 0;
    }
    protected void insert(T data){
        head.add(data);
        filterup(head.size()-1);
    }
    @Override
    public String toString(){
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<head.size();i++){
            stringBuilder.append(head.get(i)+" ");
        }
        return stringBuilder.toString();
    }
    public static void main(String[] args){
        int i;
        int a[]={10,40,30,60,90,70,20,50,80};
        MaxHeap<Integer> tree=new MaxHeap();
        System.out.println("== 依次添加: ");
        for( i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
            tree.head.add(a[i]);
        }
        System.out.println("");
        System.out.println("==添加最大堆  "+tree.toString());
        i=85;
        tree.insert(i);
        System.out.println("==添加元素: "+i);
        System.out.println("==最大堆     "+tree.toString());
        i=90;
        tree.remove(i);
        System.out.println("==删除元素: "+i);
        System.out.println("==最大堆     "+tree.toString());
    }
}