Java中PriorityQueue實現最小堆和最大堆的用法
學習很多算法知識，力爭做到最優解的學習過程中，很多時候都會遇到PriorityQueue（優先隊列）。一個基于優先級堆的無界優先級隊列。優先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的 Comparator 進行排序，具體取決于所使用的構造方法。優先級隊列不允許使用 null 元素。依靠自然順序的優先級隊列還不允許插入不可比較的對象，這樣做可能導致 ClassCastException。
此隊列的頭是按指定排序方式確定的最小元素。如果多個元素都是最小值，則頭是其中一個元素——選擇方法是任意的。隊列獲取操作 poll、remove、peek 和 element 訪問處于隊列頭的元素。優先級隊列是無界的，但是有一個內部容量，控制著用于存儲隊列元素的數組大小。它通常至少等于隊列的大小。隨著不斷向優先級隊列添加元素，其容量會自動增加。無需指定容量增加策略的細節。
此類及其迭代器實現了Collection和Iterator接口的所有可選方法。方法 iterator() 中提供的迭代器不保證以任何特定的順序遍歷優先級隊列中的元素。如果需要按順序遍歷，請考慮使用 Arrays.sort(pq.toArray())。此實現不是同步的，如果多個線程中的任意線程修改了隊列，則這些線程不應同時訪問PriorityQueue實例。相反，請使用線程安全的PriorityBlockingQueue 類。
PriorityQueue翻譯為優先隊列，“優先”指元素在隊列中按一定的順序（優先級）進行存放，“隊列”指一種先進先出的數據結構。因此PriorityQueue可以實現按照一定的優先級存取元素。
從源碼來看PriorityQueue的構造方法：
//默認容量為 11private 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 compatibilityif (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 <= 100000 <= 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最小最大堆內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！
相關文章：
網公網安備