/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package lab10heap;

/**
 *
 * @author usci
 */
public class BinaryHeap {
    private Object[] maxHeap;
    private int size=0;
    public BinaryHeap(){
        this(10);
    }
    public BinaryHeap(int i){
        size=0;
        maxHeap = new Object[i];
    }
    public void buildHeap(int[] a,int size){
        int i;
        for(i=size/2;size>=0;i--){
            reHeap(a,i,size);
        }
    }
    public void reHeap(int[] a,int root,int size){
        int maxChild,tmp;
        boolean isHeap=false;
        while((!isHeap)){
            if(2*root+1==size){
                maxChild=2*root+1;
            }
            else{
                if(a[2*root+2]>a[2*root+1]){
                    maxChild = 2*root+2;
                }
                else{
                    maxChild = 2*root+1;
                }
            }
            if(a[maxChild]>a[root]){
                tmp=a[root];
                a[root]=a[maxChild];
                a[maxChild]=tmp;
            }
            else{
                isHeap=true;
            }
        }
    }
    public void add(int a){
        maxHeap[size]=a;
        size++;
        if(size>maxHeap.length/2){
            expandHeap();
        }
        reHeapUp();
    }
    public void remove(int a){
        int i,index=-1;
        for(i=0;i<size;i++){
            if(maxHeap[i].equals(a)){
                index=i;
                break;
            }
        }
        if(index==-1){
            return;
        }
        removeIndex(i);
    }
    public void removeIndex(int a){
        if(a==size){
            maxHeap[a]=null;
            return;
        }
        maxHeap[a]=maxHeap[size-1];
        maxHeap[size-1]=null;
        size--;
        reHeapDown();
    }
    public boolean isEmpty(){
        return size==0;
    }
    public void reHeapUp(){
        int index=size-1,parent=(index-1)/2,tmp;
        boolean isHeap=false;
        while(parent>=0&&(!isHeap)){
            if((int)maxHeap[parent]<(int)maxHeap[index]){
                tmp=(int)maxHeap[parent];
                maxHeap[parent]=maxHeap[index];
                maxHeap[index]=tmp;
                index=parent;
                parent=(index-1)/2;
            }
            else{
                isHeap=true;
            }
        }
    }
    public void reHeapDown(){
        int i,maxChild,tmp;
        for(i=0;i<size&&2*i+2<size;){
            if((int)maxHeap[2*i+1]>(int)maxHeap[2*i+2]){
                maxChild=2*i+1;
            }
            else{
                maxChild=2*i+2;
            }
            if((int)maxHeap[maxChild]>(int)maxHeap[i]){
                tmp=(int)maxHeap[i];
                maxHeap[i]=maxHeap[maxChild];
                maxHeap[maxChild]=tmp;
                i=maxChild;
            }
            else{
                break;
            }
        }
    }
    public void printHeap(){
        String s="";
        int i;
        for(i=0;i<size;i++){
            System.out.print("["+i+"]\t");
        }
        System.out.println("");
        for(i=0;i<size;i++){
            System.out.print(((int)maxHeap[i])+"  \t");
        }
        System.out.println("\n");
    }
    public void expandHeap(){
        Object[] old = maxHeap;
        maxHeap = new Object[4*size];
        size=0;
        for(int i=0;i<old.length;i++){
            if(old[i]!=null){
                maxHeap[i]=old[i];
                size++;
            }
        }
    }
}