PriorityQueue实现最小堆和最大堆的用法[JAVA]
2021/6/27 11:14:17
本文主要是介绍PriorityQueue实现最小堆和最大堆的用法[JAVA],对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、基本介绍
1、介绍
PriorityQueue翻译为优先队列,“优先”指元素在队列中按一定的顺序(优先级)进行存放,“队列”指一种先进先出的数据结构。因此PriorityQueue可以实现按照一定的优先级存取元素。
2、用法
从源码来看PriorityQueue的构造方法:
//默认容量为 11 private static final int DEFAULT_INITIAL_CAPACITY = 11;
//1、无参构造,默认容量和默认排序方法 public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } //2、指定容量 public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } //3、指定排序方法 public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } //4、指定容量和排序方法 public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
由上可知,在构造PriorityQueue时我们可以指定初始容量和元素在队列中的排序方法,若不指定,则默认初始容量为11,默认排序方法为将元素从小到大进行排序。
3、最小堆
构造最小堆:
PriorityQueue<Integer> minheap = new PriorityQueue<>();
使用无参构造,元素在队列中默认按照从小到大的顺序排列,可保证每次出队列的元素为队列中的最小元素。
4、最大堆
PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());
将排序方法指定为反序,即元素从大到小排列,可保证每次出队列的元素为队列中最大的元素。
5、其他优先级
按照其他优先级规则排序,需要自己实现Comparable接口,重写compareTo()方法。
Comparable<Integer> comparable = new Comparable<Integer>() { @Override public int compareTo(Integer o) { return 0; } };
二、常用方法
以Integer类型为例:
三、相关练习题
【剑指 Offer 40. 最小的k个数】
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
限制:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
【解题思想】
先将k个数放进最大堆,再从第k+1个数开始比较,若其小于大堆顶则加入堆,堆顶出队列,若大于等于则无作为。
【代码】
class Solution { public int[] getLeastNumbers(int[] arr, int k) { int res[] = new int[k]; int len = arr.length; if(len == 0 || k == 0) return res; PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for(int i = 0; i < k; i++){ maxHeap.add(arr[i]); } for(int i = k; i < len; i++){ if(arr[i] < maxHeap.peek()){ maxHeap.add(arr[i]); maxHeap.poll(); } } for(int i = 0; i < k; i++){ res[i] = maxHeap.poll(); } return res; } }
时间复杂度:O(nlogn)
这篇关于PriorityQueue实现最小堆和最大堆的用法[JAVA]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-06数据结构和算法面试题详解与实战
- 2024-11-06数据结构与算法面试题详解及练习
- 2024-11-06网络请求面试题详解及实战技巧
- 2024-11-06数据结构和算法面试真题详解及备考指南
- 2024-11-06数据结构与算法面试真题解析与练习指南
- 2024-11-06网络请求面试真题详解及实战攻略
- 2024-11-06数据结构和算法大厂面试真题详解与实战
- 2024-11-06数据结构与算法大厂面试真题详解及入门攻略
- 2024-11-06网络请求大厂面试真题详解及应对策略
- 2024-11-06TS大厂面试真题解析与实战指南