Java中PriorityQueue實現最小堆和最大堆的用法

Posted on by

一、基本介紹

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

由上可知，在構造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）

到此這篇關於Java中PriorityQueue實現最小堆和最大堆的用法的文章就介紹到這瞭,更多相關Java PriorityQueue最小最大堆內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：