目錄
1.優先級隊列
2.?堆的概念
3. 堆的存儲方式
4. 堆的創建
4.1 向下調整
4.2 堆的創建
4.3 堆的插入
4.4 堆的刪除
5.用堆模擬實現優先級隊列
6.常用接口的介紹
6.1 PriorityQueue 的特性
6.2?PriorityQueue 的方法
7. Top?K問題
1.優先級隊列
隊列是一種先進先出的數據結構，這種數據類型每次元素的入隊和出隊都只能分別在隊尾和隊頭進行，但在一些情況，人們并不需要隊列的第一個元素，需要操作的數據可能帶有優先級，所以在出隊的時候，可能需要優先級更高的元素先出隊列。比如外賣派單系統，平臺需要快速分配最近的訂單，此時需要根據距離的遠近優先分配，這個時候優先級就是距離。
優先級隊列，它并不是隊列隊列，不滿足先進先出的條件，可以把它理解為一個堆，堆頂元素就是放優先級更高的元素，在加入元素時，堆的狀態也要根據新加元素來判斷調整優先級元素，而不是單單的指隊列的隊頭或者隊尾元素 。所以，優先級隊列滿足兩個基本操作，一是返回最高優先級對象，二是添加新的對象。
2.?堆的概念
如果一個關鍵碼的集合 K = {k0, k1, k2, k3, ..., kn - 1}，把它的所有元素按照完全二叉樹的順序存儲方式存儲在一個一維數組中，并滿足 Ki <= K2i + 1 且 Ki <= K2i + 2（或：Ki >= K2i + 1 且 Ki >= K2i + 2）?，稱為小堆（或：大堆）。根節點是所有節點最小的堆叫做最小堆或小根堆，根節點是所有節點最大的堆叫做最大堆或大根堆。
堆的性質：
- 堆的一棵完全二叉樹
- 堆中的節點的值一定不大于或不小于其父親節點的值
3. 堆的存儲方式
堆是一棵完全二叉樹，所有可以采用層序遍歷的方式進行高效存儲。
對于普通的二叉樹，并不適用順序方式進行存儲，為了更好地還原二叉樹，空間就需要存儲二叉樹的空節點，這樣會導致空間利用率降低。
如果定義根節點的下標從 0 開始，即 i 是數組的下標，那么對于任一節點 i ，它的雙親節點下標是 ( i - 1 ) / 2 ( i != 0)，左孩子節點下標是 2 * i + 1 ( 2 * i + 1 < 節點個數)，右孩子節點下標是 2 * i + 2 ( 2 * i + 2 < 節點個數)。
4. 堆的創建
4.1 向下調整
對于給定一個集合{1，20，15，18，16，12，13，8，9}，怎么把它建成一個大根堆呢？
觀察可以發現，這個數組集合除了根節點外，其余節點已經基本滿足大根堆的條件，這個時候只需要把根節點向下調整。
步驟（這里是建大根堆）：
假設根節點設為 parent 用來標記需要調整的節點，child 標記根節點的左孩子（根據完全二叉樹可以知道如果根節點存在孩子節點，那么一定擁有左孩子），孩子節點 child 不能大于數組長度，即 child < size，則有：
- 如果 parent 的左孩子存在，并且判斷是否存在右孩子，如果沒有右孩子，則 parent 和左孩子節點比較，如果 parent ＜ child，進行交換，否則不交換；如果有右孩子，左孩子和右孩子作比較，找到它們的最大值，然后再比較孩子節點和雙親節點的大小，如果滿足雙親結點小于孩子節點，進行交換，否則不交換；
- 不論是否交換，比較過后，雙親節點 parent 都要指向較小的值，然后繼續向下調整，即 parent = child，child = 2 * parent + 1;
- 重復上述步驟，知道調整比較到最后一個葉子節點位置
這種比較是次數是根據二叉樹的高度來確定，所有它的時間復雜度是0(log N)。
4.2 堆的創建
上述例子是在基本有序的情況下，只需要小幅度調整就可以完成。那么對于普通的序列{1，9，8，12，16，13，15，20，17}，怎么才能把它創建成一個大根堆呢？
對這個序列初始化堆如下：
要解決這個問題，就要找到最后一個非葉子節點的下標，最后一個非葉子節點也就是最后一個葉子節點的的雙親結點，然后和它的左右孩子作比較，如果雙親結點小于孩子節點，就做交換，交換后檢查被交換的子樹，如果被交換的子樹結構被破壞，需要遞歸下沉調整，最后再找上一個非葉子節點，重復上述步驟，直到調整到根節點為止。
代碼：
public class Heap {public int[] elem;public int usedSize;//堆的元素個數public Heap() {this.elem = new int[10];//初始化數組大小}//創建堆public void createHeap(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}//usedSize - 1 是最后一個節點的下標，for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {shiftDown(parent , usedSize);}}//交換public void swap(int[] elem , int i , int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}//向下調整private void shiftDown(int parent,int usedSize) {int child = 2 * parent + 1;//標記左孩子的位置while (child < usedSize) {//if里面的條件不能交換，比較先判斷右孩子節點是否存在if (child + 1 < usedSize && elem[child] < elem[child + 1]) {//如果有右孩子并且右孩子大于左孩子，更改孩子的位置child++;}if (elem[parent] < elem[child]) {//如果雙親節點小于孩子節點，交換swap(elem , child , parent);//交換后更新雙親結點和孩子節點parent = child;child = 2 * parent + 1;} else {//如果雙親結點大于孩子節點，不需要做交換break;}}}
}4.3 堆的插入
如果要在下面這棵樹插入一個 25?的節點的節點，應該怎么操作呢？
上面的二叉樹，根據層序遍歷的結果就是 20，18，15，9，16，12，13，8，1，其底層是數組實現的，要插入元素是25，觀察 25 比任何元素都大，那是不是把所有的元素后移一位，任何 25 插入到第一個位置就行呢？也就是：
如果這么操作之后，那么這個堆就不再是大根堆了，很明顯不符合。可以換一個角度思考，既然堆是完全二叉樹，那么新插入的元素就緊接著最后應該元素追加就好了（也就是堆的末尾），然后把這個新加入的節點和它的雙親節點作對比，如果比雙親節點大，那么就進行交換，然后更新這個新加入節點的下標，直到和根節點左比較為止
所以，堆的插入應該要滿足：
- 把新加的元素放入堆的末尾，雖然堆的本質是二叉樹，但是它是根據數組來實現的，所以在末尾追加時先判斷數組是否已滿
- 將新加的元素節點進行向上調整，直到滿足堆的性質
代碼：
//新增元素后也要滿足大根堆public void offer(int val) {if (isFull()) {//如果滿，擴容this.elem = Arrays.copyOf(elem , 2 * elem.length);}elem[usedSize] = val;//在末尾追加shiftUp(usedSize);//調用向上調整usedSize++;//元素個數加1}//向上調整，新增的元素位置為孩子節點private void shiftUp(int child) {int parent = (child - 1) / 2;//找到雙親節點while (parent >= 0) {if (elem[parent] < elem[child]) {//孩子節點大于雙親節點，進行交換swap(elem , child , parent);child = parent;parent = (child - 1) / 2;} else {//如果孩子節點不大于雙親節點，則說明新加的元素在末尾追加時，就已經滿足大根堆的性質break;}}}//判滿public boolean isFull() {return usedSize == elem.length;}
4.4 堆的刪除
堆的刪除，刪除的是堆頂元素，這也正是設計堆的原因，希望在第一個元素就可以找到優先級更高的元素。查看元素時，查看的也是堆頂元素。如何實現呢？
堆的刪除并不能說像鏈表一樣刪除頭節點，改變頭節點的指向，在這里也就是后面的元素依次往前挪，這樣是不行的，因為也會破壞堆的結構。其實可以先想一下刪除后的結果：堆的元素個數一定會減 1 ，那么只需要把原本的堆中最后一個元素的位置和堆頂元素的位置交換一下，此時對交換后的堆頂元素發生向下調整，就可以完成操作。
代碼：
//刪除元素，刪除之后也要滿足大根堆public int poll() {checkEmpty();//判斷是否為空int val = elem[0];swap(elem , 0 , usedSize-1);shiftDown(0 , usedSize-1 );usedSize--;return val;}public boolean isEmpty() {return usedSize == 0;}//判斷是否為空，如果空就沒有元素可以刪public void checkEmpty() throws EmptyException{if (isEmpty()) {throw new EmptyException("數組為空！！！");}}//查看堆頂元素public int peek() {checkEmpty();return elem[0];}
5.用堆模擬實現優先級隊列
實現優先級隊列，其實就是創建堆的過程。
6.常用接口的介紹
6.1 PriorityQueue 的特性
Java集合框架提供了?PriorityQueue 和?PriorityBlockingQueue 兩種類型的優先級隊列，?PriorityQueue 是線程不安全的，?PriorityBlockingQueue 是線程安全的。在這里主要了解??PriorityQueue。
注意事項：
1. PriorityQueue 中的元素是需要可以比較大小的，如果插入的對象不能比較大小，就會拋出 ClassCastException 異常
2. 不能插入 null 對象，否則會拋出 NullPointerException
3. 沒有容量限制，可以插入任意多個元素，其內部自動擴容（源碼如下）并且從源碼中可以看出，在優先級隊列中，如果容量小于 64 時，擴容是 2 倍擴容，如果容量大于 64 時，按照 1.5 倍擴容
4. 插入和刪除的時間復雜度都是O(log N)
5.?PriorityQueue 底層是的數據結構是堆，并且默認情況下是最小堆/小根堆，即堆頂元素是最小的元素
6.2?PriorityQueue 的方法
構造方法：
常用方法：
7. Top?K問題
Top K問題通常指從一個數據集中找出前 K 個最大（或最小）的元素，或出現頻率最高（或最低）的 K 個元素。
想要找到一組數據中前 K 個最大（或最小）的元素，或出現頻率最高（或最低）的 K 個元素，一種非常暴力的解法就是對這組數組進行排序，然后找到前 K 個元素即可，但是如果數據量非常大的時候，想要把所有數據一下子全部加載到內存的時候，可能無法實現。這時候就可以用堆的方式來解決。但還要一個問題，既然建立堆，那是把所有的數據都建立成堆嗎？如果數據非常龐大，那肯定也建立不起來，所以最好的方法就是把這組數據的前 K 個元素建立成堆，然后遍歷剩下的 N - K 個元素和堆頂元素作比較，是要較大值還是較小值，根據需求而定。
已經知道了用堆可以解決這類問題，但是在解決之前還有一個問題要解決。就是堆是用來排序的，有大根堆和小根堆，如果要找前 K 個最小的元素，是建立大根堆還是小根堆呢？仔細想想堆的性質，如果是建立小根堆，那么堆頂元素永遠是最小值，建立小根堆的目的是堆頂元素就是優先級較高的元素，想要求前 K 個最小的元素，但是當一個剩下的 N- K 個元素和堆頂做比較時，可能比堆頂元素大，但是否比除了堆頂元素之外的元素小，這個情況是沒辦法判斷的，因為堆只能瞄到堆頂元素。所以如果要找前 K 個最小的元素，應該建立大根堆。
建立大堆后，遍歷剩下的 N - K個元素和堆頂元素作比較，如果比堆頂元素還小，遍歷到符合條件的元素加入，把堆頂元素刪除，直到遍歷整組數據結束。?
總結：
求前 K 個最大元素，建立小根堆
求前 K 個最小元素，建立大根堆
最小 K 個數?:
代碼（求前K個最小元素）：
//自定義實現一個比較接口類，因為PriorityQueue默認是升序，即建立的是小根堆，與題意要求相反，所以需要重新定義比較接口
class IntCom implements Comparator<Integer> {@Overridepublic int compare(Integer o1 , Integer o2) {return o2.compareTo(o1);}
}
public class Main {public static int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if(arr == null || k == 0){return ret;}//方法：建立一個大小為K的大根堆，然后遍歷N-K個元素，PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k , new IntCom());//調用比較方式//把前K個元素建立大根堆for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}//遍歷剩下的N - K個元素for (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();//看堆頂元素的值if (arr[i] < peekVal) {//如果遍歷的元素小于堆頂元素，堆頂元素刪除，新元素加入priorityQueue.poll();priorityQueue.offer(arr[i]);}}//走到這里，說明現在的堆中所有元素就是需要的前K個最小元素//堆新堆進行遍歷，因為要返回前K個最小的元素for (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}Arrays.sort(ret);return ret;}public static void main(String[] args) {int[] array = {1 , 9 , 15 , 36 , 66 , 88 , 99 , 42 , 8 , 7};int[] ret = smallestK(array , 3);for (int num : ret) {System.out.print(num + " ");}}
}輸出結果：
（感謝閱讀，文章較長，如有錯誤，還望指正！撒花???）
學習記錄)
