package shujujiegou.二叉树;

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

/*
最大优先队列 由 二叉堆的最大堆完成。
*/
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) {
    //队列超出内容 扩容
    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保存插入的叶子节点值，用于最后的赋值。
    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保存父节点的值 用于最后的赋值
    int temp =array[childIndex];

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

}