優先級隊列（堆）PriorityQueue

1:左子樹結點=父節點2+1 右子樹結點=父節點2+2

已經知道孩子結點是i。則父節點是(i-1)/2.

2：堆其實就是一顆完全二叉樹，儲存在數組中，主要是為了找到數組中的最值。分為大堆和小堆

3：向下調整：以大堆為例：找到最後一課子樹的根節點，然後比較根節點和子節點的值，誰大放到根節點，然後父節點在指向被換的子節點，繼續判斷。小堆的話 從最上面開始比較，比較根和左右的大小，誰小就放在根，然後根指向被換的子節點。

4：堆的應用：入堆：向上調整。以大堆為例，誰大就放在根節點，然後讓孩子等于父親，父親繼續往上。

出堆：向下調整。直接讓第一個數字和最後一個數字交換位置，然後向下調整，長度減一。

5：一個一個出堆：一直重複交換第一個和最後一個元素，然後向下調整，長度減一。每調整一次結束，就繼續重複，繼續長度減去一，這樣就都出堆了。

6：TOPK問題

TOPK問題 100萬個資料中 去找前10個最大的或者前10個最小的1；建堆 找最大 就開始建大小為10的小堆，從第11個開始，每個資料和目前堆頂元素比較，如果比堆頂元素大，那麼堆中的元素出隊，然後把目前元素放進這個堆裡。

求前10個最小的就建一個大堆

求前10個最大的就建一個小堆

這種問題的思路：1：先建立一個大堆。代碼：

PriorityQueue maxHeap=new PriorityQueue<>(k, new Comparator() {

public int compare(Integer o1, Integer o2) {

return o2-o1;//大堆就是o2-o1

}

})；

此時大堆的代碼已經建立好了，要注意引用Comparator

2:周遊整個數組，看看前10個數字是否填滿，沒有就先填滿。

3：滿了就讓第11個數字與根比較，如果i第11個值小，就與根結點交換。