目錄一、基本介紹 1、介紹2、用法3、最小堆4、最大堆5、其他優(yōu)先級二、常用方法三、相關(guān)練習(xí)題一、基本介紹 1、介紹

學(xué)習(xí)很多算法知識，力爭做到最優(yōu)解的學(xué)習(xí)過程中，很多時(shí)候都會遇到PriorityQueue（優(yōu)先隊(duì)列）。一個(gè)基于優(yōu)先級堆的無界優(yōu)先級隊(duì)列。優(yōu)先級隊(duì)列的元素按照其自然順序進(jìn)行排序，或者根據(jù)構(gòu)造隊(duì)列時(shí)提供的 Comparator 進(jìn)行排序，具體取決于所使用的構(gòu)造方法。優(yōu)先級隊(duì)列不允許使用 null 元素。依靠自然順序的優(yōu)先級隊(duì)列還不允許插入不可比較的對象，這樣做可能導(dǎo)致 ClassCastException。

此隊(duì)列的頭是按指定排序方式確定的最小元素。如果多個(gè)元素都是最小值，則頭是其中一個(gè)元素——選擇方法是任意的。隊(duì)列獲取操作 poll、remove、peek 和 element 訪問處于隊(duì)列頭的元素。優(yōu)先級隊(duì)列是無界的，但是有一個(gè)內(nèi)部容量，控制著用于存儲隊(duì)列元素的數(shù)組大小。它通常至少等于隊(duì)列的大小。隨著不斷向優(yōu)先級隊(duì)列添加元素，其容量會自動增加。無需指定容量增加策略的細(xì)節(jié)。

此類及其迭代器實(shí)現(xiàn)了Collection和Iterator接口的所有可選方法。方法 iterator() 中提供的迭代器不保證以任何特定的順序遍歷優(yōu)先級隊(duì)列中的元素。如果需要按順序遍歷，請考慮使用 Arrays.sort(pq.toArray())。此實(shí)現(xiàn)不是同步的，如果多個(gè)線程中的任意線程修改了隊(duì)列，則這些線程不應(yīng)同時(shí)訪問PriorityQueue實(shí)例。相反，請使用線程安全的PriorityBlockingQueue 類。

PriorityQueue翻譯為優(yōu)先隊(duì)列，“優(yōu)先”指元素在隊(duì)列中按一定的順序（優(yōu)先級）進(jìn)行存放，“隊(duì)列”指一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。因此PriorityQueue可以實(shí)現(xiàn)按照一定的優(yōu)先級存取元素。

2、用法

從源碼來看PriorityQueue的構(gòu)造方法：

//默認(rèn)容量為 11private static final int DEFAULT_INITIAL_CAPACITY = 11;

//1、無參構(gòu)造，默認(rèn)容量和默認(rèn)排序方法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 compatibilityif (initialCapacity < 1) throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator; }

由上可知，在構(gòu)造PriorityQueue時(shí)我們可以指定初始容量和元素在隊(duì)列中的排序方法，若不指定，則默認(rèn)初始容量為11，默認(rèn)排序方法為將元素從小到大進(jìn)行排序。

3、最小堆

構(gòu)造最小堆：

PriorityQueue<Integer> minheap = new PriorityQueue<>();

使用無參構(gòu)造，元素在隊(duì)列中默認(rèn)按照從小到大的順序排列，可保證每次出隊(duì)列的元素為隊(duì)列中的最小元素。

4、最大堆

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

將排序方法指定為反序，即元素從大到小排列，可保證每次出隊(duì)列的元素為隊(duì)列中最大的元素。

5、其他優(yōu)先級

按照其他優(yōu)先級規(guī)則排序，需要自己實(shí)現(xiàn)Comparable接口，重寫compareTo()方法。

Comparable<Integer> comparable = new Comparable<Integer>() { @Override public int compareTo(Integer o) {return 0; }};二、常用方法

以Integer類型為例：

三、相關(guān)練習(xí)題

【劍指 Offer 40. 最小的k個(gè)數(shù)】

輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個(gè)數(shù)。例如，輸入4、5、1、6、2、7、3、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是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 <= 100000 <= arr[i] <= 10000

【解題思想】

先將k個(gè)數(shù)放進(jìn)最大堆，再從第k+1個(gè)數(shù)開始比較，若其小于大堆頂則加入堆，堆頂出隊(duì)列，若大于等于則無作為。

【代碼】

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; } }

時(shí)間復(fù)雜度：O（nlogn）

到此這篇關(guān)于Java中PriorityQueue實(shí)現(xiàn)最小堆和最大堆的用法的文章就介紹到這了,更多相關(guān)Java PriorityQueue最小最大堆內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！