/**
 * use maximum-top heap to implement priority queue
 * define a MAX_SIZE_OF_PRIORITY_QUEUE to limit the max length of priority queue
 * use a integer array to store element
 * hypothesis i is the root node and then use 2*i to mark left child and 2*i+1 to mark right child
 * use initialArray[0] to store the length of heap
 * */
public class PriorityQueue{
    private static final int MAX_SIZE_OF_PRIORITY_QUEUE=100;
    private int[] initialArray;
    /**
     * initial priority queue with a exist array which can't be null
     * */
    public PriorityQueue(int[] initialElement) {
        if(initialElement==null)return;
        if(initialElement.length==0)return;
        initialArray=new int[MAX_SIZE_OF_PRIORITY_QUEUE];
        initialArray[0]=initialElement.length;
        for(int i=0;i<initialElement.length;i++)initialArray[i+1]=initialElement[i];
        System.out.println(initialArray[0]);
        for (int i = initialArray[0]; i >0 ; i--)reBuildHeap(i);
    }
    /**
     * rebuild array according to the value of each node
     * maximum-top heap
     * index represents the index of a node which should be rebuild(include it's children node)
     *
     * simple:
     *         1
     *      2     3
     *   4   5  6   7
     *
     * */
    private void reBuildHeap(int index){
        System.out.println("execute rebuild function to rebuild a maximum-top heap with one loop");
        int leftChildIndex=index*2;
        int rightChildIndex=leftChildIndex+1;
        int length=initialArray[0];
        int biggerValueIndex=-1;
        if(leftChildIndex>length&&rightChildIndex>length){
            System.out.println("no left child");
            return;
        }
        if(leftChildIndex<=length&&rightChildIndex>length){
            System.out.println("only left child");
            biggerValueIndex=leftChildIndex;
        }
        if(leftChildIndex>length&&rightChildIndex<=length){
            System.out.println("only right child");
            biggerValueIndex=rightChildIndex;
        }
        if(leftChildIndex<=length&&rightChildIndex<=length){
            System.out.println("both children");
            biggerValueIndex=initialArray[leftChildIndex]>initialArray[rightChildIndex]?leftChildIndex:rightChildIndex;
        }
        if(initialArray[index]>initialArray[biggerValueIndex]){
            System.out.println("unnecessary to swap!");
            return;
        }else{
            int temp=initialArray[index];
            initialArray[index]=initialArray[biggerValueIndex];
            initialArray[biggerValueIndex]=temp;
            this.reBuildHeap(biggerValueIndex);
        }
    }
    public int getLength() {
        return initialArray[0];
    }
    /**
     * get top priority value of heap
     * the first element of array
     * */
    public int priority(){
        return initialArray[1];
    }
    /**
     * length++
     * add element to the tail of array
     * rebuild the heap to regular priority heap
     * */
    public void insert(int element){
        initialArray[0]++;
        initialArray[initialArray[0]]=element;
        for(int i=initialArray[0];i>=1;i=i/2){
            reBuildHeap(i);
        }
    }
    /**
     * length--
     * swap the first element and last element
     * delete last value
     * rebuild the heap
     * */
    public int deletePriority(){
        if(initialArray[0]<=0)return -1;
        int maxValue=initialArray[1];
        initialArray[1]=initialArray[initialArray[0]];
        initialArray[0]--;
        for(int i=initialArray[0];i>=1;i=i/2){
            reBuildHeap(i);
        }
        return maxValue;
    }
    /**
     * print the structure of priority heap
     * */
    @Override
    public String toString() {
        StringBuilder builder=new StringBuilder("{");
        for (int i = 1; i <= initialArray[0]; i++) {
            if(i!=1)builder.append(",");
            builder.append(initialArray[i]);
        }
        builder.append("}");
        return builder.toString();
    }
}