4.2 手写Java PriorityQueue 核心源码

上一节介绍了PriorityQueue的原理，先来简单的回顾一下 PriorityQueue 的原理

以最大堆为例来介绍

PriorityQueue是用一棵完全二叉树实现的。
不但是棵完全二叉树，而且树中的每个根节点都比它的左右两个孩子节点元素大
PriorityQueue底层是用数组来保存这棵完全二叉树的。

如下图，是一棵最大堆。

最大堆的删除操作 删除指的是删除根元素，也就是图中的100元素删除元素也就是 shiftDown 操作，向下翻删除一个根元素有以下步骤：

将100元素删除，将最后一个元素12放到100的位置上，12成为根节点
找出 12 这个节点的左右两个孩子节点中的最大的，也就是图中的28节点
12 出 28节点进行比较，如果12比28小，则交换位置
12节点继续重复2，3步骤，直到12比它的左右孩子节点都大则停止

最大堆插入一个节点 插入一个节点，也叫shiftUp操作，向上翻以插入一个节点23为例，步骤如下：

将23放到二叉树的最后位置，也就是成为了9这个节点的左孩子
23与它的父节点进行比较，如果比它的父节点大，就交换位置
23这个节点继续重要第2步骤，直到比它的父节点小方停止比较

代码实现 首先我们先上两张图

我们从左往右，按层序遍历，分别存放到数组的相应索引对应的位置上。数组的第0个索引位置我们不用，从索引为1的位置开始存放。最终这个最大堆存放到数组中，如下图

首先实现一个最简单的只存 int 类型的优先级队列 QPriorityQueueInt 完整代码如下：

1//最大堆,只存放int，并且没有扩容机制
2public class QPriorityQueueInt {
3    //默认底层数据大小为10
4    private static int DEFAULT_INIT_CAPACITY = 10;
5
6    //底层数组
7    private int[] queue;
8
9    //节点的个数
10    private int size;
11
12    public QPriorityQueueInt() {
13        //因为数组是从索引 1 的位置开始存放，索引为 0 的位置不用
14        //所以开辟空间的时候需要加 1
15        queue = new int[DEFAULT_INIT_CAPACITY + 1];
16
17        //当前数组中节点的个数为0
18        size = 0;
19    }
20
21    //返回节点的个数
22    public int size() {
23        return size;
24    }
25
26    //最大堆是否为空
27    public boolean isEmpty() {
28        return size == 0;
29    }
30
31    //添加一个节点
32    public void add(int e) {
33        //将元素存放到数组当前最后一个位置上
34        queue[size + 1] = e;
35
36        //个数需要加1
37        size++;
38
39        //需要向上翻
40        shiftUp(size);
41    }
42
43    //向上翻，最大堆中的最后一个节点，不停的与父节点比较
44    //最大堆中父节点的索引是 k / 2
45    private void shiftUp(int k) {
46        // k > 1 ，说明从第2个节点开始，因为如果只有一个节点的话，不需要比较了
47        // queue[k] > queue[k / 2] ，当前节点大于父节点
48        while (k > 1 && queue[k] > queue[k / 2]) {
49            //交换位置
50            swap(k, k / 2);
51
52            //把父节点的索引赋值给 k,然后继续重复上面步骤
53            k = k / 2;
54        }
55    }
56
57    //删除最大堆中的节点
58    public int poll() {
59
60        //把第1个位置的节点保存起来
61        int result = queue[1];
62
63        //把最后一个节点放到第1个节点上面，成为整棵树的根节点
64        queue[1] = queue[size];
65
66        //别忘了size 要减1
67        size--;
68
69        //最后一个节点成为根节点后，就需要向下翻了
70        //向下翻的目的就是把大的节点翻上来
71        shiftDown(1);
72
73        //返回第1个节点，也就是队头节点
74        return result;
75    }
76
77
78    //向下翻
79    private void shiftDown(int k) {
80        //2 * k <= size ，2*k 是左孩子
81        //2 * k <= size ，是当前节点有左孩子
82        //至少有个左孩子才可以交换，因为是完全二叉树，左孩子没有，右孩子肯定没有
83        while (2 * k <= size) {
84
85            //比较左右两个孩子节点，将大的节点的索引赋值给 j
86
87            //左孩子索引
88            int j = 2 * k;
89            //如果有右孩子，且 右孩子大于左孩子，将右孩子索引赋值给j
90            if (j + 1 <= size && queue[j + 1] > queue[j]) {
91                j = j + 1;
92            }
93
94            //现在 j 保存的是左右孩子中较大的节点的索引
95            //比较当前节点和左右孩子中较大的节点
96            //如果比左右孩子中较大的节点还大，则不用向下翻了
97            if (queue[k] > queue[j]) {
98                break;
99            }
100
101            //否则交换当前节点和左右孩子中较大的节点
102            swap(k, j);
103
104            //把左右孩子中较大的节点的索引赋值给k，继续向下翻
105            k = j;
106        }
107    }
108
109    //交换两个位置
110    private void swap(int i, int j) {
111        int t = queue[i];
112        queue[i] = queue[j];
113        queue[j] = t;
114    }
115
116}
117

下面是测试代码：

1public static void main(String[] args) {
2    QPriorityQueueInt queue = new QPriorityQueueInt();
3
4    //随便弄5个数入队，数越大优先级越大
5    //由于我们的QPriorityQueueInt默认只支持10个元素
6    //所以插入的节点个数不要多于10个
7    queue.add(3);
8    queue.add(5);
9    queue.add(1);
10    queue.add(8);
11    queue.add(7);
12
13    //打印
14    System.out.println(queue.poll());
15    System.out.println(queue.poll());
16    System.out.println(queue.poll());
17    System.out.println(queue.poll());
18    System.out.println(queue.poll());
19}
20

输出如下：

从输出可以看出来，虽然7是最后入队的，但是优先级比较高，第二次就打印出来了。优先级队列，同样是用数组实现。但是入队的效率比单纯的用数组排序要高多了。

至于扩容机制，读者可以自己查阅相关资源，自己实现。

4.2 手写Java PriorityQueue 核心源码

评论区

相关推荐