package shujujiegou.二叉樹;

import java.util.Arrays;
import java.util.PriorityQueue;

/*
最大優(yōu)先隊列 由 二叉堆的最大堆完成。
*/
public class PriorityQueueMax {
private int[] array;
private int size;

public PriorityQueueMax() {
    //隊列初始化長度為32
    this.array  =new int[32];
}

public static void main(String[] args) throws Exception {

    PriorityQueueMax  priorityQueue=new PriorityQueueMax();
    //入隊
    priorityQueue.enQueue(3);
    priorityQueue.enQueue(5);
    priorityQueue.enQueue(10);
    priorityQueue.enQueue(2);
    priorityQueue.enQueue(7);

    System.out.println("出隊元素"+priorityQueue.deQueue());
    System.out.println("出隊元素"+priorityQueue.deQueue());
}



/*
       入隊
 */
private void enQueue(int key) {
    //隊列超出內(nèi)容 擴容
    if (size >=array.length){
        resize();
    }
    array[size++]=key;
    upAdjust();
}

/*
隊列擴容
*/
private void resize() {
//隊列容量翻倍
int newSize=this.size * 2;
this.array= Arrays.copyOf(this.array, newSize);
}

/*
    上沉操作
 */
private void upAdjust() {
    int childrenIndex = array.length-1;
    int parentIndex = (childrenIndex-1)/2;

    //temp保存插入的葉子節(jié)點值，用于最后的賦值。
    int  temp  = array[childrenIndex];

    while (temp >  array[parentIndex] &&  childrenIndex >0){
        //無需真正交換 單向賦值即可
        array[childrenIndex]  =array[parentIndex];
        childrenIndex=parentIndex;
        parentIndex=parentIndex/2;
    }
        array[childrenIndex]=temp;
    System.out.println(Arrays.toString(array));
}
/*
     出隊
 */
private int deQueue() throws Exception {
    if (size<=0){
        throw new Exception("the queue is empty!");
    }
    //獲取堆頂元素
    int head=array[0];

    //讓最后一個元素移動到堆頂
    array[0]=array[--size];
    downAdjust();
    return head;
}

/**
 * 下沉操作
 */
private void downAdjust() {
    int childIndex =1;
    int parentIndex =0;
    //temp保存父節(jié)點的值 用于最后的賦值
    int temp =array[childIndex];

    while (childIndex < size){
        //如果有右孩子 且 右孩子大于左孩子的值 則定位到右孩子
        if (childIndex +1 < size  &&  array[childIndex+1] > array[childIndex]){
            childIndex++;
        }
        //如果父節(jié)點 大于 任何 一個 孩子 的值  直接跳出
        if (temp >= array[childIndex]){
            break;
        }
        array[parentIndex]  =array [childIndex];
        parentIndex =childIndex;
        childIndex = 2* childIndex +1;
    }
    array[parentIndex] =temp;
}

}