上海建站模板系统,百度的网址是什么,唐山医疗网站建设,旅游网站设计源码优先级队列#xff08;Priority Queue#xff09;是一种特殊的队列类型#xff0c;它允许在其元素中分配优先级。与传统的先进先出#xff08;FIFO#xff09;队列不同#xff0c;优先级队列中元素的出队顺序取决于它们的优先级。优先级较高的元素会被优先处理#xff0… 优先级队列Priority Queue是一种特殊的队列类型它允许在其元素中分配优先级。与传统的先进先出FIFO队列不同优先级队列中元素的出队顺序取决于它们的优先级。优先级较高的元素会被优先处理即使它们是在优先级较低的元素之后被加入队列的。
优先级队列的特点
插入操作新元素被添加到队列中时它们根据自身的优先级被放置在适当的位置。移除操作优先级队列通常移除并返回具有最高优先级的元素。查询操作可以查询具有最高优先级的元素而不从队列中移除它。
在Java中的实现
Java标准库中的java.util.PriorityQueue类提供了一个基于优先级的队列实现。PriorityQueue底层使用了一种称为“堆”的数据结构通常是二叉堆以确保高效地维护元素的优先级顺序。
import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个优先级队列PriorityQueueInteger 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) {// 创建一个优先级队列使用自定义比较器PriorityQueueString priorityQueue new PriorityQueue(new ComparatorString() {Overridepublic 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]
思路: 统计元素出现的频率 对频率进行排序 找出前k个高频元素
构建一个优先级队列【小顶堆】遍历map将二元组存入小顶堆中【以频率进行排序】维护优先级队列的长度为k当有比小顶堆顶堆大的元素直接弹出堆顶并加入新的节点。最后优先级队列中保存的就是前k高频的元素直接弹出即可。 public int[] topKFrequent(int[] nums, int k) {//1.使用map统计元素出现频率HashMapInteger,Integer map new HashMap();for(int num : nums){map.put(num,map.getOrDefault(num,0) 1);}//2.将map中的元素以二元组的形式放入优先级队列中并以频率为目标构建小顶堆PriorityQueueint[] queue new PriorityQueue((pair1, pair2) -pair1[1] - pair2[1]);//遍历map放入优先级队列中for (EntryInteger, 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.依次弹出小顶堆中的keyint[] res new int[k];int size queue.size();for (int i 0; i size; i) {res[i] queue.poll()[0];}return res;}
