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

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

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

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

1
//向下调整方法(复杂度logN)
2
    public static void shiftDown(int[] array, int index){
3
        //要调整的父节点
4
        int parent = index;
5
        //要调整的孩子节点
6
        int child = 2*parent + 1;
7
        while (child < array.length){
8
            //child+1其实代表的是右子树
9
            //判断左右子树大小
10
            if(child+1<array.length && array[child+1] < array[child]){
11
                //左右子树对调
12
                child = child+1;
13
            }
14
            //判断左子树和父节点的大小
15
            if (array[child] >= array[parent]){
16
                break;
17
            }
18
            else{
19
                int temp = array[parent];
20
                array[parent] = array[child];
21
                array[child] = temp;
22
                //更新父节点和子节点的指向
23
                parent = child;
24
                child = 2*parent +1;
25
            }
26
        }
27
    }
28

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