1.優先級佇列概述

PriorityQueue，即優先佇列，優先佇列的作用是能保證每次取出的元素都是佇列中權值最小的（Java的優先佇列每次取最小元素，C++的優先佇列每次取最大元素），這里牽涉到了大小關系，元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構造時傳入的比較器（Comparator，類似于C++的仿函式），

Java中PriorityQueue實作了Queue介面，不允許放入null元素；其通過堆實作，具體說是通過完全二叉樹（complete binary tree）實作的小頂堆（任意一個非葉子節點的權值，都不大于其左右子節點的權值），也就意味著可以通過陣列來作為PriorityQueue的底層實作，

2.優先級佇列的操作方法

堆疊中的插入和移除資料項的命名一般都是 push、pop，而佇列至今沒有標準化的命名，插入操作可以用 add、offer等命名，移除操作可以用 poll、remove、等命名，查看隊頭操作可以用 peek、element等命令，
Java中PriorityQueue實作了Queue介面，Queue介面實作了Collection介面，所以PriorityQueue包含了collection介面的add,remove,element方法
在 Java 中，常見的佇列操作以及它們的區別如下所示：

操作	方法名	描述
插入	offer	向佇列插入元素，在一個滿的佇列中加入一個新項會回傳false
插入	add	向佇列插入元素，在一個滿的佇列中加入一個新項會拋出例外
洗掉	poll	從佇列中洗掉第一個元素，在佇列為空時回傳null
洗掉	remove	從佇列中洗掉第一個元素，在佇列為空時會拋出例外
查看隊頭元素	peek	在佇列的頭部查詢元素，在佇列為空時回傳null
查看隊頭元素	element	從佇列中洗掉第一個元素，在佇列為空時會拋出例外

3.優先級佇列的應用

3.1.最小K個數

3.1.1.問題描述

設計一個演算法，找出陣列中最小的k個數，以任意順序回傳這k個數均可，
示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4
輸出： [1,2,3,4]

提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

3.1.2.解題思路及實作代碼

我們用一個小根堆(優先級佇列)實時維護陣列的前 k 小值，首先將陣列中的全部元素壓入堆中(優先級佇列)，然后出隊k個元素即可，求得最小的k個元素

class Solution {
    public int[] smallestK(int[] arr, int k) {
        Queue<Integer> queue=new PriorityQueue<Integer>();      //優先級佇列
        int len=arr.length;
        for(int i=0;i<len;i++){             //將陣列中元素入隊
            queue.offer(arr[i]);
        }
        int [] result=new int[k];
        for(int i=0;i<k;i++){               //出隊k個元素
            result[i]=queue.poll();
        }
        return result;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258462.html

標籤：其他

上一篇：Nginx專題：Nginx安裝后常用功能配置