初识数据结构——优先级队列（堆！堆！堆！）

// 堆的数组表示
parent(i) = (i-1)/2  // 找父节点
left(i) = 2*i + 1    // 左孩子
right(i) = 2*i + 2    // 右孩子

// 向下调整示例（小根堆）
void shiftDown(int[] arr, int parent, int len) {
    int child = 2*parent + 1;
    while (child < len) {
        // 找出较小的孩子
        if (child+1 < len && arr[child+1] < arr[child]) child++;
        // 如果父节点已经比孩子小，调整结束
        if (arr[parent] <= arr[child]) break;
        swap(arr, parent, child);  // 交换父子
        parent = child;            // 继续向下调整
        child = 2*parent + 1;
    }
}

// 大根堆实现
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);

// 自定义对象排序
PriorityQueue<Student> pq = new PriorityQueue<>(
    (s1, s2) -> s1.score != s2.score ? 
        s2.score - s1.score :  // 分数高的在前
        s1.name.compareTo(s2.name)  // 分数相同按名字
);

//向下调整方法(复杂度logN)
    public static void shiftDown(int[] array, int index){
        //要调整的父节点
        int parent = index;
        //要调整的孩子节点
        int child = 2*parent + 1;
        while (child < array.length){
            //child+1其实代表的是右子树
            //判断左右子树大小
            if(child+1<array.length && array[child+1] < array[child]){
                //左右子树对调
                child = child+1;
            }
            //判断左子树和父节点的大小
            if (array[child] >= array[parent]){
                break;
            }
            else{
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                //更新父节点和子节点的指向
                parent = child;
                child = 2*parent +1;
            }
        }
    }

    /**
     *建堆操作复杂度O(n)
     * @param array
     */
    public static void createHeap(int[] array){
        //要先找到最后一个非叶子节点
        int lastLeaf  = array.length-1;
        int lastParent = (lastLeaf-1)/2;
        for (int i = lastParent; i >= 0; i--){
            shiftDown(array, i);
        }
    }