数据结构-PriorityQueue

1. 概念

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。优先级队列中的元素按照优先级进行排序，具有更高优先级的元素会在队列中被优先处理。

2. 优先级队列的模拟实现

2.1 堆的概念

PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

• 完全二叉树：堆是完全二叉树，通常用数组表示。
• 堆性质：
  • 最大堆：每个父节点的值大于或等于其子节点的值，根节点是最大值。
  • 最小堆：每个父节点的值小于或等于其子节点的值，根节点是最小值。

2.2 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子

    70
   /  \
  56   30
 / \   / \
10  15 25 10
Array: [70, 56, 30, 10, 15, 25, 10]

2.3 堆的创建

2.3.1 堆的向下调整

假设我们有以下一个二叉树:

    10
   /  \
  56   30
 / \   / 
10  15 25 

数组表示为: [10, 56, 30, 10, 15, 25]

根节点的左右子树已经完全满足堆的性质，现在·需要将根节点进行向下调整操作来维护堆的性质。

向下调整的过程如下:

1. 由于 10 不满足最大堆的性质,需要向下调整。
2. 将 10 与它的左右子节点中较大的一个(56)交换。
3. 继续向下调整,直到满足最大堆的性质。

调整后的堆结构如下:

    56
   /  \
  15   30
 / \   / 
10  10 25 

数组表示为: [56, 15, 30, 10, 10, 25]

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

时间复杂度分析：

最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为$O(logn)$

2.3.2 堆的创建

1. 将输入数组中的元素按照从上到下、从左到右的顺序存储在数组中。
2. 从最后一个非叶子节点开始,对每个节点进行向下调整,使其满足最大堆或最小堆的性质。

我们以 最大堆 为例，按照步骤进行堆的创建，给出调整过程以及对应的图示。

输入数组：1, 5, 3, 8, 7, 6

步骤 1：将数组元素按照从上到下、从左到右的顺序存储在完全二叉树中。

初始的完全二叉树表示如下（数组索引从 0 开始）：

          1
       /    \
      5      3
     / \    /
    8   7  6

步骤 2：从最后一个非叶子节点开始向下调整

最后一个非叶子节点的索引为：(n / 2) - 1，其中 n 为数组长度。
对于数组 [1, 5, 3, 8, 7, 6]，n = 6，所以最后一个非叶子节点为索引 2，对应值为 3。

调整过程

1. 从索引 2 开始调整（值为 3）

比较当前节点与其子节点，发现 6 > 3，需要交换。

          1
       /    \
      5      6
     / \    /
    8   7  3

2. 调整索引 1（值为 5）

比较当前节点与其子节点，发现 8 > 5，需要交换。

          1
       /    \
      8      6
     / \    /
    5   7  3

继续向下调整索引 3（值为 5）：
当前节点 5 没有子节点，无需调整。

3. 调整索引 0（值为 1）

比较当前节点与其子节点，发现 8 > 1，需要交换。

          8
       /    \
      1      6
     / \    /
    5   7  3

继续向下调整索引 1（值为 1）：

比较当前节点与其子节点，发现 7 > 1，需要交换。

          8
       /    \
      7      6
     / \    /
    5   1  3

继续向下调整索引 4（值为 1）：
当前节点 1 没有子节点，无需调整。

这种创建方式的时间复杂度为 O(n),比逐个插入元素的方式 O(n log n) 更加高效。

2.4 堆的插入与删除

2.4.1 堆的插入

1. 先将元素放到底层空间中，即最后一个孩子之后，
2. 插入之后如果堆的性质遭到破坏，将新插入的节点顺着其双亲往上调整到适当位置即可

堆的插入操作是向堆中添加一个新元素，并调整堆的结构以保持堆的性质（最大堆或最小堆）。我们以 最大堆 为例，演示插入的过程。

假设初始最大堆如下：

          8
       /    \
      7      6
     / \    /
    5   1  3

插入新元素

假设我们要插入新元素 9。

步骤 1：将新元素插入到堆的最后一个位置

          8
       /    \
      7      6
     / \    / \
    5   1  3   9

步骤 2：向上调整（Heapify Up）

从插入的节点开始，逐层向上调整，以满足最大堆的性质。

1. 当前节点为索引 6（值为 9），其父节点为索引 2（值为 6）。
   比较 9 > 6，需要交换。

          8
       /    \
      7      9
     / \    / \
    5   1  3   6
   

2. 当前节点为索引 2（值为 9），其父节点为索引 0（值为 8）。
   比较 9 > 8，需要交换。

          9
       /    \
      8      7
     / \    / \
    5   1  3   6
   

3. 当前节点为索引 0（值为 9），已经是根节点，无需继续调整。

2.4.2 堆的删除

堆的删除操作一般是指删除堆顶元素（最大堆中删除最大值或最小堆中删除最小值），并调整堆的结构以保持堆的性质。

1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整

我们以 最大堆 为例，演示删除堆顶元素的过程。

假设初始最大堆如下：

          9
       /    \
      8      7
     / \    / \
    5   1  3   6

删除堆顶元素（最大值）

步骤 1：将堆顶元素（9）删除，并用最后一个元素代替堆顶

• 删除堆顶元素 9。
• 将最后一个元素 6 移到堆顶。

          6
       /    \
      8      7
     / \    /
    5   1  3

步骤 2：向下调整（Heapify Down）

从新的堆顶开始，逐层向下调整，以满足最大堆的性质。

比较 6 与其子节点，发现 8 > 6，需要交换。

       8
    /    \
   6      7
  / \    /
 5   1  3

比较 6 与其子节点，发现 6 > 5 和 6 > 1，无需交换。调整结束。

2.5 堆的模拟实现

package myDataStructure.Heap;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * @Author: Author
 * @CreateTime: 2025-03-23
 * @Description:
 */
public class MyMaxHeap {
    private int[] heap; // 用于存储堆的数组
    private int size;   // 当前堆的大小
    // 构造函数
    public MyMaxHeap() {
        // 初始化堆的容量和数组
        heap=new int[10];
    }
    // 辅助交换方法
    private void swap(int i,int j){
        int temp=heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
    }

    // 插入元素到堆中
    public void insert(int value) {
        expandCapacity();
        size++;
        // 插入操作
        heap[size-1]=value;
        heapifyUp(size-1);
    }

    // 删除堆顶元素（最大值）
    public int removeMax() {
        if (size==0) {
            throw new NoSuchElementException("Heap is empty, no maximum element available.");
        }
        int removedValue=heap[0];
        swap(0,size-1);
        heap[size-1]=0; // 清理无效数据
        size--;
        heapifyDown(0);
        return removedValue; // 占位返回值
    }

    // 获取堆顶元素（最大值）
    public int getMax() {
        if (size==0) {
            throw new NoSuchElementException("Heap is empty, no maximum element available.");
        }
        return heap[0];
    }

    // 获取当前堆的大小
    public int getSize() {
        return size;
    }

    // 判断堆是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 打印堆内容（可选，用于调试）
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    // 向上调整（用于插入操作）
    private void heapifyUp(int child) {
        while(child!=0){
            int parent=(child-1)/2;
            if (heap[child]>heap[parent]) {
                swap(child, parent);
                child=parent;
            }
            else {
                break;
            }
        }
    }

    // 向下调整（用于删除操作）
    private void heapifyDown(int parent) {
        while(true){
            int leftChild=parent*2+1;
            int rightChild=parent*2+2;
            int largest=parent;
            if (leftChild<size&&heap[leftChild]>heap[largest]){
                largest=leftChild;
            }
            if (rightChild<size&&heap[rightChild]>heap[largest]){
                largest=rightChild;
            }
            if (parent==largest){
                return;
            }
            swap(parent,largest);
            parent=largest;
        }
    }

    private void expandCapacity(){
        if (size==heap.length)
        {
            heap= Arrays.copyOf(heap,size*3/2);
        }
    }
}

class MyMaxHeapTest {
    public static void main(String[] args) {
        // 创建一个最大堆实例
        MyMaxHeap heap = new MyMaxHeap();

        // 测试用例 1: 插入元素并打印堆
        System.out.println("测试用例 1: 插入元素并打印堆");
        heap.insert(10);
        heap.insert(20);
        heap.insert(5);
        heap.insert(30);
        heap.insert(15);
        heap.printHeap(); // 期望输出: [30, 20, 5, 10, 15]

        // 测试用例 2: 获取堆顶元素
        System.out.println("\n测试用例 2: 获取堆顶元素");
        System.out.println("堆顶元素: " + heap.getMax()); // 期望输出: 30

        // 测试用例 3: 删除堆顶元素并打印堆
        System.out.println("\n测试用例 3: 删除堆顶元素并打印堆");
        System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 30
        heap.printHeap(); // 期望输出: [20, 15, 5, 10]

        // 测试用例 4: 连续删除堆顶元素
        System.out.println("\n测试用例 4: 连续删除堆顶元素");
        System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 20
        System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 15
        heap.printHeap(); // 期望输出: [10, 5]

        // 测试用例 5: 插入更多元素并检查扩容
        System.out.println("\n测试用例 5: 插入更多元素并检查扩容");
        heap.insert(50);
        heap.insert(40);
        heap.insert(60);
        heap.insert(70);
        heap.insert(80);
        heap.insert(90);
        heap.insert(100);
        heap.printHeap(); // 期望输出: [100, 80, 90, 70, 40, 60, 50, 10, 5]

        // 测试用例 6: 获取堆的大小
        System.out.println("\n测试用例 6: 获取堆的大小");
        System.out.println("堆大小: " + heap.getSize()); // 期望输出: 9

        // 测试用例 7: 判断堆是否为空
        System.out.println("\n测试用例 7: 判断堆是否为空");
        System.out.println("堆是否为空: " + heap.isEmpty()); // 期望输出: false

        // 测试用例 8: 清空堆后操作
        System.out.println("\n测试用例 8: 清空堆后操作");
        while (!heap.isEmpty()) {
            System.out.println("删除的堆顶元素: " + heap.removeMax());
        }
        heap.printHeap(); // 期望输出: []

        // 测试用例 9: 空堆操作异常处理
        System.out.println("\n测试用例 9: 空堆操作异常处理");
        try {
            heap.getMax();
        } catch (Exception e) {
            System.out.println("异常捕获: " + e.getMessage()); // 期望输出: Heap is empty. Current size: 0
        }
        try {
            heap.removeMax();
        } catch (Exception e) {
            System.out.println("异常捕获: " + e.getMessage()); // 期望输出: Heap is empty. Current size: 0
        }
    }
}

3. PriorityQueue

3.1 PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

图片

1. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
2. 不能插入null对象，否则会抛出NullPointerException
3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
4. 插入和删除元素的时间复杂度为 $O(logN)$
5. PriorityQueue底层使用了堆数据结构
6. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素