Java中PriorityQueue实现最小堆和最大堆的用法

Java中PriorityQueue实现最小堆和最大堆的用法

一、基本介绍

1、介绍

学习很多算法知识，力争做到最优解的学习过程中，很多时候都会遇到PriorityQueue（优先队列）。一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象，这样做可能导致 ClassCastException。

此队列的头是按指定排序方式确定的最小元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。

此类及其迭代器实现了Collection和Iterator接口的所有可选方法。方法 iterator() 中提供的迭代器不保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。此实现不是同步的，如果多个线程中的任意线程修改了队列，则这些线程不应同时访问PriorityQueue实例。相反，请使用线程安全的PriorityBlockingQueue 类。

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;

BBGIcRdWN }

由上可知，在构造PriorityQueue时我们可以指定初始容量和元素在队列中的排序方法，若不指定，则默认初始容量为11，默认排序方法为将元素从小到大进行排序。

3、最小堆

构造最小堆：

PriorityQueue minheap = new PriorityQueue<>();

使用无参构造，元素在队列中默认按照从小到大的顺序排列，可保证每次出队列的元素为队列中的最小元素。

4、最大堆

PriorityQueue maxheap = new PriorityQueue<>(Collections.reverseOrder());

将排序方法指定为反序，即元素从大到小排列，可保证每次出队列的元素为队列中最大的元素。

5、其他优先级

按照其他优先级规则排序，需要自己实现Comparable接口，重写compareTo()方法。

Comparable comparable = new Comparable() {

@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

【解题思想BBGIcRdWN】

先将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 maxHeap = new PriorityQueue<>(Collections.reverseOrder());

for(int i =http:// 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();

http:// }

}

for(int i = 0; i < k; i++){

res[i] = maxHeap.poll();

}

return res;

}

}

时间复杂度：O（nlogn）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。