二叉堆：父节点的值大于或等于每个子节点的值

在一个二叉堆数组（不使用第一个元素）中，位置 k 的父节点的位置为 ⌊k/2⌋（向下取整），他的两个子节点的位置分别为 2k 和 2k + 1

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class MaxPriorityQueue<E extends Comparable<E>> {

    /**
     * 插入元素
     */
    public void insert(E e);

    /**
     * 返回最大元素
     */
    public E max();

    /**
     * 删除并返回最大元素
     */
    public E delMax();

    /**
     * 队列是否为空
     */
    public boolean isEmpty();

    /**
     * 队列元素个数
     */
    public int size();
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
public class MaxPriorityQueue<E extends Comparable<E>> {

    /**
     * 优先队列数组
     */
    private E[] priorityQueue;

    private int N = 0;

    public MaxPriorityQueue(int size) {
        priorityQueue = (E[]) new Comparable[size + 1];
    }

    public void insert(E e) {
        priorityQueue[++N] = e;
        swim(N);
    }

    /**
     * 返回最大元素
     */
    public E max() {
        if (isEmpty()) {
            throw new IllegalArgumentException("empty MaxPriorityQueue");
        }

        return priorityQueue[1];
    }

    /**
     * 删除并返回最大元素
     */
    public E delMax() {
        E max = priorityQueue[1];
        swap(1, N--); // 最后一个元素为 priorityQueue[N]，priorityQueue[N--] 先和最后一个元素交换，再减少 N
        priorityQueue[N + 1] = null; // help gc
        sink(1);
        return max;
    }

    /**
     * 队列是否为空
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 队列元素个数
     */
    public int size() {
        return N;
    }

    /**
     * 上浮
     */
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) { // k != 1，根元素不能上浮
            swap(k / 2, k);
            k /= 2;
        }
    }

    /**
     * 下沉
     */
    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            // j < N，则还有第 j + 1 个元素。
            // 如果左节点小于右节点，则 j 后移动，使 priorityQueue[k] 总是与最大的节点比较
            if (j < N && less(j, j + 1)) {
                j++;
            }
            if (!less(k, j)) { // 如果 priorityQueue[k] 的值不比最大的节点值大，则退出循环
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    /**
     * 交换 priorityQueue[i] 和 priorityQueue[j]
     */
    private void swap(int i, int j) {
        E temp = priorityQueue[i];
        priorityQueue[i] = priorityQueue[j];
        priorityQueue[j] = temp;
    }

    /**
     * 判断 priorityQueue[i] 是否小于 priorityQueue[j]
     */
    private boolean less(int i, int j) {
        return priorityQueue[i].compareTo(priorityQueue[j]) < 0;
    }

    public static void main(String[] args) {
        MaxPriorityQueue<Integer> maxPQ = new MaxPriorityQueue<>(10);

        for (int i = 0; i < 10; i++) {
            maxPQ.insert(i);
        }

        for (int i = 0; i < 10; i++) {
            System.out.print(maxPQ.delMax());
            if (i != 9) {
                System.out.print(" | ");
            }
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void main(String[] args) {
    MaxPriorityQueue<Integer> maxPQ = new MaxPriorityQueue<>(10);

    for (int i = 0; i < 10; i++) {
        maxPQ.insert(i);
    }

    for (int i = 0; i < 10; i++) {
        System.out.print(maxPQ.delMax());
        if (i != 9) {
            System.out.print(" | ");
        }
    }
}