一、基本介紹

 1、介紹

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

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

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

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

2、用法

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

//默認(rèn)容量為 11
private 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 compatibility
        if (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)先級(jí)

按照其他優(yōu)先級(jí)規(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 <= 10000
0 <= 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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論