Java中的优先级队列 PriorityQueue 与 堆

1. 优先级队列的定义

1.1 什么是优先级队列？

  优先级队列是由一组元素组成的集合，每个元素都有一个相关的优先级，优先级高的元素先出队列。

  具体来说，一个优先级队列应该支持以下操作：

1. 插入元素：将一个新元素插入到队列中，并指定它的优先级。
2. 删除最高优先级元素：从队列中删除具有最高优先级的元素，并返回它的值。

  在优先级队列中，元素的优先级决定了它们在队列中的顺序，在删除最高优先级元素后，要确保队列中剩余元素按照优先级排序。

  JDK1.8中的PriorityQueue(Java中的优先级队列)底层使用了堆这个数据结构，堆就是在完全二叉树的基础之上进行了一些元素的调整。

2. 堆

2.1 什么是堆？

  堆是一种完全二叉树，其中每个节点的值都不小于（或不大于）其子节点的值。堆分为两种类型：

1. 最大堆(大根堆)：对于每个节点，其值都大于或等于其子节点的值。
2. 最小堆(小根堆)：对于每个节点，其值都小于或等于其子节点的值。

2.2 堆的存储方式

  堆是一棵完全二叉树，因此可以按层序序列的方式用数组来存储，这样比较高效。而非完全二叉树就不适用数组来存储：

  完全二叉树能充分地利用空间。

  重要性质：

iii 表示数组的下标，nnn 表示树的总节点数：

• i=0i = 0i=0 时，iii 位置的节点为根节点；当 i≠0i \ne 0i=0 时，iii 节点的双亲节点(父节点)的下标为 (i−1)/2(i-1)/2(i−1)/2 。
• 2i+1<n2i+1 < n2i+1<n 时，2i+12i+12i+1 就是它的左孩子下标；2i+1≥n2i+1 \ge n2i+1≥n 时，iii 节点没有左孩子。
• 2i+2<n2i+2 < n2i+2<n 时，2i+22i+22i+2 就是它的右孩子下标；2i+2≥n2i+2 \ge n2i+2≥n 时，iii 节点没有右孩子。

  这些性质非常重要，请大家熟记。

2.3 堆的创建

  我们已经熟悉了堆的一些性质，那么我们就开始来创建一个堆，由于堆是一棵：每个节点的值都不小于（或不大于）其子节点的值完全二叉树，所以要想创建一个堆，我们就得把一个序列(完全二叉树)调整为前面性质的完全二叉树。

2.3.1 堆的向下调整

  给定一棵完全二叉树：{27,15,19,18,28,34,65,49,25,37}，现在要求调整为一个大根堆(每个节点的值都大于子节点的值)。

（注意：把一棵完全二叉树调整为大根堆或小根堆 都是用向下调整法，这里以大根堆为例）

原图：

  怎么调整？

1. 首先我们得从树的最后一个节点开始向下调整，相当于从数组的最后一个元素往前遍历；
2. 当前节点是否有孩子节点，没有则往前走；如果有，则把以当前节点为根节点的子树调整为一个堆：
   • 比较当前节点和其两个子节点的大小，找到其中最大(或最小)的节点，将当前节点和最大(或最小)的子节点交换位置，并递归地对被交换的子节点进行向下调整(也可以不用递归)，直到当前节点已经成为最大或最小的节点为止。
   • 如果根节点本来就最大，往前走。
3. 遍历完数组后，调整结束。

动图：

我们来模拟实现堆。

建堆：

public class MyHeap {
 
    public int[] data;
 
    public int usedSize;//有效的数据个数
 
    public MyHeap(){
        data = new int[10];
    }
 
    //通过传递数组的方式初始化data
    public void initData(int[] arr){
        this.data = Arrays.copyOf(arr,arr.length);
        usedSize = arr.length;
    }
    
 
    //打印这个堆
    public void print(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(data[i] + " ");