package huffman;

public class Heap {
    Node[] a;
    int size;
    int maxsize;
    public Heap(Node[] newArray, int newSize){
        a=newArray; //array where the heap is stored
        size = newSize; // current number of elements in the heap
        maxsize = a.length-1; // maximum number of elements in the heap
        if (size>maxsize) // probably should handle this with exception
            System.out.println("heap overflow");
    }
    public void makeHeap() {
        for (int i=size/2; i>0; i--)
            trickle(i);
    }        
    public Node extractMin() {
        if (size < 1) // probably should handle this with exception
            System.out.println("heap underflow");
        Node max = a[1];
        a[1]=a[size];
        a[size]=null; // for garbage collection
        size--;
        trickle(1);
        return max;
    }    

    public void insert(Node z) {
        if (size >= maxsize) // probably should handle this with exception
            System.out.println("heap overflow");
        size++;
        a[size]=z;
        percolate(size);   
    }
    public void trickle(int p) {
        int left = 2*p;
        int right = left+1;
        int smallest;
        if (left <= size && a[left].freq<a[p].freq)
            smallest = left;
        else smallest = p;
        if (right <= size && a[right].freq<a[smallest].freq)
            smallest = right;
        if (smallest != p) {
            Node n = a[p];
            a[p] = a[smallest];
            a[smallest] = n;
            trickle(smallest);
        }
    } 
    public void percolate(int p) {
        while (p>1 && a[p/2].freq > a[p].freq) {
            Node n = a[p/2];
            a[p/2] = a[p];
            a[p] = n;
            p=p/2;
        }
        
    }    
    public void printContents(){
        for (int i=1; i<=size; i++)
            System.out.println(a[i].freq);
    }
}