package heap;

import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * Maximum Heap
 * @author Winston Prakash
 */
public class MaximumHeap {
    int[] heapData;
    int dataSize;
    int dataCapacity;
    /** Creates a new instance of MaxHeap */
    public MaximumHeap(int[] data) {
        heapData = new int[data.length];
        System.arraycopy(data, 0, heapData, 0, data.length);
        dataSize = heapData.length;
    }
    
    public MaximumHeap(int capacity){
        dataCapacity = capacity;
        heapData = new int[capacity];
        dataSize = 0;
    }
    
    public void setSize(int size){
        dataSize = size;
    }
    
    public int getSize(){
        return dataSize;
    }
    
    public int[] getHeapData(){
        return heapData;
    }
    public int getParentIndex(int index){
        return (index - 1)/2; //(index >> 1) - 1;
    }
    
    public int getLeftChildIndex(int index){
        return (2 * index) + 1; //(index << 1) - 1;
    }
    
    public int getRightChildIndex(int index){
        return (2 * index) + 2;// (index << 1) ;
    }
    
    /**
     * Need to build from N/2 to 1 only as children won't
     * exist if index is greater than N/2
     * (2 * index + 1) must be less than N
     */
    public void build(){
        for(int i = dataSize/2 - 1; i >= 0; i--){
            floatDownValue(i);
        }
    }
    
    /**
     * Insert at the end of the heap data array and then try float up
     * the value
     */
    public void insert(int value){
        if (dataSize < dataCapacity){
            if (dataSize > 0){
                heapData[dataSize++] = value;
                floatUpValue(dataSize - 1);
            }else{
                heapData[dataSize++] = value;
            }
        }
    }
    
    /**
     * Make sure the Max Heap is built already
     */
    public int extractMax(){
        int max = heapData[0];
        heapData[0] = heapData[dataSize - 1];
        dataSize--;
        floatDownValue(0);
        return max;
    }
    
    /**
     * Replace the current value in the index.
     * If the value is greater than old value try float up
     * else try float down.
     */
    public void modifyValue(int index, int value){
        int oldValue = heapData[index];
        heapData[index] = value;
        if(value > oldValue){
            floatUpValue(index);
        }else{
            floatDownValue(index);
        }
    }
    
    /**
     * If the parent is greater than index value then recursively
     * exchange value with parent.
     */
    public void floatUpValue(int index){
        if(index > 0){
            int parentIndex = getParentIndex(index);
            int indexData = heapData[index];
            if(heapData[parentIndex] < heapData[index]){
                heapData[index] = heapData[parentIndex];
                heapData[parentIndex] = indexData;
                floatUpValue(parentIndex);
            }
        }
    }
    
    /**
     * Maintain the heap property by flotaing down the indexed value
     * if the heap property (children are less than paren) is is not
     * satisfied.
     * If one or both children are greater than index value then recursively
     * exchange value with larger child.
     */
    public void floatDownValue(int index){
        if(index > (dataSize/2 -1)) return;
        int leftChildIndex = getLeftChildIndex(index);
        int rightChildIndex = getRightChildIndex(index);
        int indexData = heapData[index];
        int largeChildIndex;
        // Make sure right child exists
        if( rightChildIndex <  dataSize &&
                heapData[leftChildIndex] < heapData[rightChildIndex]){
            largeChildIndex = rightChildIndex;
        }else{
            largeChildIndex =  leftChildIndex;
        }
        // if child is greater sift it up.
        if (heapData[index] < heapData[largeChildIndex]){
            heapData[index] =  heapData[largeChildIndex];
            heapData[largeChildIndex] = indexData;
            floatDownValue(largeChildIndex);
        }
    }
    
    public void displayData(){
        int log2 = 0;
        int count = 0;
        for (int i = 0; i < dataSize; i++){
            System.out.print( i + "=" + heapData[i] +  "  ");
            if (i == count){
                System.out.println();
                count = (i + 1) * 2;
            }
        }
        System.out.println("\n\n");
    }
}