【算法】优先级队列-基础与应用

优先级队列（Priority Queue）是一种特殊的队列类型，它允许在其元素中分配优先级。与传统的先进先出（FIFO）队列不同，优先级队列中元素的出队顺序取决于它们的优先级。优先级较高的元素会被优先处理，即使它们是在优先级较低的元素之后被加入队列的。

优先级队列的特点：

• 插入操作：新元素被添加到队列中时，它们根据自身的优先级被放置在适当的位置。
• 移除操作：优先级队列通常移除并返回具有最高优先级的元素。
• 查询操作：可以查询具有最高优先级的元素，而不从队列中移除它。

在Java中的实现：

Java标准库中的java.util.PriorityQueue类提供了一个基于优先级的队列实现。PriorityQueue底层使用了一种称为“堆”的数据结构，通常是二叉堆，以确保高效地维护元素的优先级顺序。

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个优先级队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 插入元素
        priorityQueue.add(5);
        priorityQueue.add(1);
        priorityQueue.add(3);
        priorityQueue.add(4);
        priorityQueue.add(2);

        // 查看并移除优先级最高的元素
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

在这个例子中，PriorityQueue默认使用元素的自然排序（对于基本类型或实现了Comparable接口的对象）。如果需要自定义排序规则，可以通过构造函数传递一个Comparator实例。

自定义排序：

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个优先级队列，使用自定义比较器
        PriorityQueue<String> priorityQueue = 
            new PriorityQueue<>(new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s2.compareTo(s1); // 反向排序
                }
            });

        // 插入元素
        priorityQueue.add("Z");
        priorityQueue.add("A");
        priorityQueue.add("C");

        // 查看并移除优先级最高的元素
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

性能：

PriorityQueue提供了高效的插入和移除操作，时间复杂度通常为O(log n)，其中n是队列中的元素数量。这是因为堆数据结构能够有效地维护元素之间的优先级关系，同时保持操作效率。

大顶堆/小顶堆

前K个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路:

• 1. 统计元素出现的频率
• 2. 对频率进行排序
• 3. 找出前k个高频元素

构建一个优先级队列【小顶堆】，遍历map，将二元组存入小顶堆中【以频率进行排序】，维护优先级队列的长度为k，当有比小顶堆顶堆大的元素，直接弹出堆顶并加入新的节点。最后优先级队列中保存的就是前k高频的元素，直接弹出即可。

 public int[] topKFrequent(int[] nums, int k) {

    //1.使用map统计元素出现频率
    HashMap<Integer,Integer> map =  new HashMap<>();
    for(int num : nums){
        map.put(num,map.getOrDefault(num,0) + 1);
    }

    //2.将map中的元素以二元组的形式放入优先级队列中，并以频率为目标构建小顶堆
    PriorityQueue<int[]> queue = new PriorityQueue<>((pair1, pair2) ->
            pair1[1] - pair2[1]);
    //遍历map，放入优先级队列中
    for (Entry<Integer, Integer> entry : map.entrySet()){
        //小顶堆的大小小于k,直接放入
        if (queue.size() < k){
            queue.add(new int[]{entry.getKey(),entry.getValue()});
        }else {
            //小顶堆的大小大于k,与堆顶比较，如果大于堆顶，则弹出堆顶并加入堆
            if (queue.peek()[1] < entry.getValue()){
                queue.poll();
                queue.add(new int[]{entry.getKey(),entry.getValue()});
            }
        }
    }

    //3.依次弹出小顶堆中的key
    int[] res =  new int[k];
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        res[i] = queue.poll()[0];
    }

    return res;

}