【Java/数据结构】优先级队列（PriorityQueue）

本博客将介绍优先级队列的概念、原理、实现、使用。

一.优先级队列概述

什么是优先级队列？

我们知道一般的队列有先进先出（FIFO）规则，但是有的情况下并非先进先出，而是有优先顺序，如就诊，病危病人要优先就诊，一般病人则按顺序（先进先出就诊），于是优先级队列应运而生。

优先级队列：每个元素被赋予一个“优先级值”，队列根据该值动态调整元素的出队顺序。核心特性是 元素按优先级顺序出队

他有2个基本操作，一是返回最高优先级对象，一是插入元素。

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

优先级队列实际上是基于堆（基于顺序结构的有序完全二叉树）：

其具有基于数组的二叉树的特性：

• 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2。
• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子。
• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子。

上图等价于：

我们规定根节点的优先级最高，出队意味着删除根节点，删除根节点后就意味着下一个最高优先级的数据要上浮，由此展开的堆重排序是我们要考虑的重难点：

（1）基本结构

这里我们实现的是小根堆，即最小值在根节点 

public class MyPriorityQueue {
    private int[] heap;
    private int size;
    private int capacity;

    // 构造函数，初始化指定容量的优先级队列
    public MyPriorityQueue(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 辅助方法，获取父节点索引
    private int parent(int index) {
        return (index - 1) / 2;
    }

    // 辅助方法，获取左子节点索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 辅助方法，获取右子节点索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    
    // 辅助方法，交换指定下标元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    ......

（2）插入元素

 新元素我们添加到末层末尾，然后对他执行上浮操作，即让他到合适的位置去，

// 插入元素
public void insert(int value) {
    if (size == capacity) {
        throw new IllegalStateException("Priority queue is full");
    }
    heap[size] = value;    //层插法，在最后一层末尾添加
    siftUp(size);          //新元素上浮，直到堆有序
    size++;
}

上浮操作我们使用一个循环，当当前元素不为根节点或者大于父亲节点，那么就要继续上浮，上浮我们调用了辅助方法，交换两位置即可，然后更新当前位置的指针为原父亲节点， 

// 上浮操作，维护堆性质
private void siftUp(int index) {
    while (index > 0 && heap[parent(index)] > heap[index]) {
        swap(parent(index), index);
        index = parent(index);
    }
}

请看一下示例：

（3）提取并删除堆顶元素

删除元素我们不能直接删除，因为一旦堆顶空缺，再想把堆重排序为有序就会相当困难，于是根据堆是一颗完全二叉树的特性，我们可以把队尾元素和队首元素交换，出队尾元素，然后对堆顶（原队尾元素）进行下沉，下沉到合适位置，这样就能在改变少数节点的情况下使堆有序。

// 提取最小元素
public int extractMin() {
    if (size == 0) {
        throw new IllegalStateException("Priority queue is empty");
    }
    int result = heap[0];
    heap[0] = heap[size - 1];
    size--;
    siftDown(0);    //对原队尾、现堆顶元素进行下沉操作
    return result;
}

在下沉时，首先找到孩子节点中数值较小的元素， 然后再让找到的元素上浮一层

private void siftDown(int parent) {
    int child = (2*parent)+1;    // 左孩子下标
    while (child < size) {       // 确保孩子节点存在
        if(child+1 < size && heap[child] > heap[child+1]) {
            child++;             // 确保child一定是 左右孩子最大值的下标
        }

        if(heap[child] < heap[parent]) {
            swap(child, parent);
            parent = child;
            child = 2*parent+1;
        }else {
            //已经有序了
            break;
        }
    }
}

请看实例：

（4）其他方法

// 获取最小元素
public int peek() {
    if (size == 0) {
        throw new IllegalStateException("Priority queue is empty");
    }
    return heap[0];
}

// 获取队列大小
public int size() {
    return size;
}

// 检查队列是否为空
public boolean isEmpty() {
    return size == 0;
}

三.PriorityQueueAPI的使用

请参考以下代码：

import java.util.PriorityQueue;

public class PriorityQueueDemo {

    public static void main(String[] args) {
        // 1. 创建优先级队列（默认最小堆，最小元素优先）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 2. 添加元素 - offer() 或 add()
        minHeap.offer(5);
        minHeap.add(3);
        minHeap.offer(8);
        minHeap.add(1);
        minHeap.offer(4);
        
        // 输出: [1, 3, 8, 5, 4] - 注意toString()不保证完全有序，但保证堆顶是最小元素
        System.out.println("当前队列: " + minHeap);
        
        // 3. 获取队列大小 - 输出: 5
        System.out.println("队列大小: " + minHeap.size());
        
        // 4. 查看队首元素（不删除） - 输出: 1
        System.out.println("队首元素(peek): " + minHeap.peek());
        
        // 5. 取出队首元素（删除） - 输出: 1
        System.out.println("取出元素(poll): " + minHeap.poll());
        // 取出后队列大小 - 输出: 4
        System.out.println("取出后的队列大小: " + minHeap.size());
        
        // 6. 遍历队列 - 输出顺序可能是: 3 4 8 5 （不保证完全有序）
        System.out.print("遍历队列: ");
        for (Integer num : minHeap) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        // 7. 检查是否包含某元素 - 输出: true 和 false
        System.out.println("是否包含3: " + minHeap.contains(3));
        System.out.println("是否包含10: " + minHeap.contains(10));
        
        // 8. 清空队列 - 输出: true
        minHeap.clear();
        System.out.println("清空后队列是否为空: " + minHeap.isEmpty());
        
        // 9. 创建最大堆（使用自定义比较器，Lambda表达式写法）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);    
        maxHeap.offer(5);  // 输出最大堆队列: [8, 3, 5]
        maxHeap.offer(3);
        maxHeap.offer(8);
        
        System.out.println("\n最大堆队列: " + maxHeap);
        // 输出最大堆队首元素: 8
        System.out.println("最大堆队首元素: " + maxHeap.peek());
        
        // 10. 其他方法演示
        System.out.println("\n其他方法演示:");
        PriorityQueue<String> stringQueue = new PriorityQueue<>();
        stringQueue.add("apple");    // 按字典序排列
        stringQueue.add("banana");
        stringQueue.add("cherry");
        
        // 输出: [apple, banana, cherry]
        System.out.println("字符串队列: " + stringQueue);
        // 输出: apple
        System.out.println("移除元素: " + stringQueue.remove());
        // 输出: [banana, cherry]
        System.out.println("剩余队列: " + stringQueue);
        
        // 11. 处理空队列情况
        PriorityQueue<Double> emptyQueue = new PriorityQueue<>();
        // 输出: null
        System.out.println("\n空队列peek(): " + emptyQueue.peek());
        // 如果执行下面这行会抛出NoSuchElementException
        // System.out.println(emptyQueue.remove());
    }
}

其他请详见：PriorityQueue (Java Platform SE 8 )

结语

本次就介绍这么多了，觉得有帮助不妨点个赞吧！下次博客应该是关于Map和Set的。好了，下次见！(*´∀ ˋ*)