一、優(yōu)先級隊(duì)列

? ? ? ? 優(yōu)先級隊(duì)列不同于隊(duì)列，隊(duì)列是先進(jìn)先出，優(yōu)先級隊(duì)列是優(yōu)先級最高的先出。一般有兩種操作：返回最高優(yōu)先級對象，添加一個(gè)新對象。

二、堆

2.1、什么是堆

? ? ? ? 堆也是一種數(shù)據(jù)結(jié)構(gòu)，是一棵完全二叉樹，該完全二叉樹中的所有子樹的根都大于其孩子，即大根堆；如果都小于其孩子，就是小根堆。

2.2、堆的存儲方式

? ? ? ? 由于完全二叉樹按層序遍歷，節(jié)點(diǎn)之間沒有空隙，所以存儲在順序表中不會造成空間浪費(fèi)；并且順序存儲方便訪問二叉樹中某節(jié)點(diǎn) i 的雙親（(i-1)/2）和孩子（左：2*i+1，右：2*i+2），以便調(diào)整堆。因此，堆采用順序結(jié)構(gòu)存儲。

? ? ? ? 大根堆示例：

三、優(yōu)先級隊(duì)列（堆）的模擬實(shí)現(xiàn)

? ? ? ?PriorityQueue 底層是用堆實(shí)現(xiàn)的。

3.1、將完全二叉樹調(diào)整為堆（向下調(diào)整）

3.1.1、手動模擬過程

調(diào)整下面的完全二叉樹為堆。

????????從最后一個(gè)父節(jié)點(diǎn)開始調(diào)整（parent=((usedSize-1)-1)/2）：將較大的孩子 child 與父節(jié)點(diǎn)比較（沒有右孩子不需要比較孩子大小），若 child 更大則于父節(jié)點(diǎn)交換。

? ? ? ? 調(diào)整倒數(shù)第 2 棵子樹（parent--）。

????????調(diào)整倒數(shù)第 3 棵子樹。

? ? ? ??調(diào)整倒數(shù)第 4 棵子樹。

? ? ? ? 如果p和c交換了，還要調(diào)整其子樹（p=c），直到 p 和 c 沒有交換為止，或者 c 超過二叉樹大小 usedSize 為止。（向下調(diào)整）

? ? ? ? 重復(fù)上述操作，直到調(diào)整完 p=0 的樹。

3.1.2、代碼實(shí)現(xiàn)

? ? ? ? 向下調(diào)整過程，時(shí)間復(fù)雜度推導(dǎo)：如果某棵子樹高為 k，則最多交換 k-1 次，高為 k 的完全二叉樹最多有 N=(2^k)-1 個(gè)結(jié)點(diǎn)，因此 k-1 = (log(N+1)-1)，時(shí)間復(fù)雜度為 O(logN)。

    /*** 向下調(diào)整* 時(shí)間復(fù)雜度：O(logN)* @param parent 子樹根節(jié)點(diǎn)的下標(biāo)* @param size 子樹的大小*/private void shiftDown(int parent, int size) {int maxChild = 2*parent+1; // 默認(rèn)最大孩子為左孩子while(maxChild < size) { // 存在左孩子就繼續(xù)調(diào)整if(maxChild+1 < size && arr[maxChild+1] > arr[maxChild]) { // 存在右孩子且右孩子大于左孩子maxChild++;}if (arr[maxChild] > arr[parent]) { // 最大孩子大于父節(jié)點(diǎn)，交換swap(parent, maxChild);parent = maxChild; // 繼續(xù)調(diào)整子樹maxChild = 2*parent+1;}else { // 沒有交換，結(jié)束調(diào)整break;}}}

? ? ? ? 將完全二叉樹調(diào)整為堆，時(shí)間復(fù)雜度推導(dǎo)：

T=1*(h-1)+2^1*(h-2)+……+2^(h-2)*1。

2T=2^1*(h-1)+2^2*(h-2)+……+2^(h-1)*1。

2T-T=T=2^1+2^2+……+2^(h-2)+2^(h-1)-h+1=2^h-1-h=2^log(N+1)-1-log(N+1)=N-log(N+1)

時(shí)間復(fù)雜度為?O(N)。

    /*** 將一棵完全二叉樹調(diào)整為大根堆* 時(shí)間復(fù)雜度：O(N)*/public void shift2Heap() {int initParent = ((usedSize - 1)-1)/2;for (int i = initParent; i >= 0; i--) {shiftDown(i, usedSize);}}

? ? ? ? 測試結(jié)果：

3.2、堆中插入一個(gè)新節(jié)點(diǎn)（向上調(diào)整）

? ? ? ? 另一種創(chuàng)建堆的方法是，每插入一個(gè)新節(jié)點(diǎn)，就調(diào)整二叉樹為堆。

3.2.1、手動模擬過程

? ? ? ? 在結(jié)尾插入新結(jié)點(diǎn)80，并從最后一棵子樹開始（child=usedSize-1），從下往上調(diào)整，直到 parent=0，或者沒有交換為止。（向上調(diào)整）

? ? ? ? child=parent。

3.2.2、代碼實(shí)現(xiàn)

? ? ? ? 向上調(diào)整：

    /*** 向上調(diào)整* 時(shí)間復(fù)雜度：O(logN)* @param child 添加的孩子節(jié)點(diǎn)的下標(biāo)*/private void shiftUp(int child) {int parent = (child-1)/2; // 父節(jié)點(diǎn)下標(biāo)while(parent >= 0 && arr[child] > arr[parent]) { // 父節(jié)點(diǎn)存在且孩子大于父節(jié)點(diǎn)，交換swap(child, parent);child = parent;parent = (child-1)/2; // 繼續(xù)向上調(diào)整}}

? ? ? ? 插入一個(gè)新節(jié)點(diǎn)：

    /*** 添加元素到堆中* 時(shí)間復(fù)雜度：O(NlogN)*/public void offer(int val) {if (isFull()) { // 數(shù)組已滿，擴(kuò)容arr = Arrays.copyOf(arr, arr.length * 2);}arr[usedSize] = val;usedSize++;shiftUp(usedSize-1); // 向上調(diào)整}

? ? ? ? 測試：

? ? ? ? 如果插入 N 個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度推導(dǎo)：

T=2*1+2^2*2+……+2^(h-2)*(h-2)+2^(h-1)*(h-1)

2T=2^2+2^3*2+……+2^(h-1)*(h-2)+2^h*(h-1)

2T-T=T=2^h*(h-1)-2^2-2^3-……-2^(h-1)-2=2^h*(h-1)-2*(2^(h-1)-1)

=2^h*(h-1)-2^h+2=2+2^h*(h-2)+2=(N+1)*(log(N+1)-2)+2

時(shí)間復(fù)雜度為：O(NlogN)

3.3、刪除堆頂元素

? ? ? ? 步驟：

• 堆頂與堆尾元素交換。
• 刪除堆尾元素。
• 對堆從樹根開始向下調(diào)整。

    public int poll() {if (isEmpty()) {return -1;}int ret = arr[0];arr[0] = arr[usedSize-1];usedSize--;shiftDown(0, usedSize); // 向下調(diào)整return ret;}

四、PriorityQueue 的使用

4.1、注意事項(xiàng)

• PriorityQueue 是線程不安全的，PriorityBlockingQueue 是線程安全的。
• PriorityQueue 中放置的元素必須是可比較大小的，否則會拋出異常。
• 不能插入 null，否則會拋出異常。

????????而我們之前學(xué)習(xí)的 LinkList 是可以插入 null 的：

• 默認(rèn)構(gòu)建小根堆。

4.2、構(gòu)造函數(shù)的使用

????????無參構(gòu)造器：默認(rèn)容量 11，默認(rèn)比較器為空。

????????帶初始容量參數(shù)的構(gòu)造器：指定初始容量，默認(rèn)比較器為空。

????????用一個(gè)集合創(chuàng)建優(yōu)先級隊(duì)列：傳入某集合對象。

? ? ? ? 因?yàn)?String 不是 Number 及其子類，所以語法錯(cuò)誤。

? ? ? ? Integer 是 Number 的子類，成功調(diào)用。

????????指定初始容量、比較器的構(gòu)造函數(shù)：

? ? ? ? transient 的作用：讓不想被序列化的屬性不被序列化，保證信息的隱私，比如密碼。序列化就是把對象的信息轉(zhuǎn)成字符串放到磁盤里；反序列化就是把磁盤里的字符串轉(zhuǎn)成對象信息。transient 就讓修飾的屬性信息的生命周期僅在調(diào)用者的內(nèi)存中，而不會寫進(jìn)磁盤中持久化。

4.3、offer 插入一個(gè)元素

? ? ? ? 插入一個(gè)元素，offer 源碼：

? ? ? ? 擴(kuò)容，grow 源碼：

? ? ? ? 向上調(diào)整，shiftUp 源碼：

? ? ? ? 如果元素是基礎(chǔ)類型的包裝類，會使用自身重寫的 compareTo：

? ? ? ? 如果構(gòu)造函數(shù)參數(shù)指定了比較器：

4.4、poll 刪除堆頂元素

? ? ? ? 刪除堆頂元素，poll 源碼：

? ? ? ? 可以看到源碼的向下調(diào)整的方法，與我們實(shí)現(xiàn)的方法大致相同。

五、OJ練習(xí)

5.1、top-k 問題：最小的 k 個(gè)數(shù)

面試題 17.14. 最小K個(gè)數(shù) - 力扣（LeetCode）

• 解法1：用排序算法，從小到大排序，取前 k 個(gè)。最快的排序算法時(shí)間復(fù)雜度 O(NlogN)。
• 解法2：創(chuàng)建小根堆，取 k 次堆頂元素，每次刪除堆頂元素后，向下調(diào)整。時(shí)間復(fù)雜度 O(NlogN)。

    /*** 方法1：使用小根堆實(shí)現(xiàn)topK小，* 時(shí)間復(fù)雜度：O(NlogN) + O(k*logN) = O(NlogN)*/public static int[] topK1(int[] arr, int k) {if(k > arr.length) { // k大于數(shù)組長度，直接返回?cái)?shù)組return arr;}if(k <= 0) { // k小于等于0，返回空數(shù)組return new int[0];}// 創(chuàng)建一個(gè)小根堆，O(NlogN)PriorityQueue<Integer> pq = new PriorityQueue<>(k);for (int x : arr) {pq.offer(x);}// 取k次堆頂元素，存入數(shù)組，O(k*logN)int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = pq.poll();}return ret;}

• 解法三：創(chuàng)建大小為 k 的大根堆，從 k?開始遍歷數(shù)組，遇到比堆頂（堆中的最大值）小的 x，就刪除堆頂，插入 x。效率最高，O(N*logk)。

    /*** 方法2：使用大根堆實(shí)現(xiàn)topK小，* 時(shí)間復(fù)雜度：O(k*logk) + O((N-k)*logk) + O(k*logk) = O(N*logk)*/public static int[] topK2(int[] arr, int k) {if(k > arr.length) { // k大于數(shù)組長度，直接返回?cái)?shù)組return arr;}if(k <= 0) { // k小于等于0，返回空數(shù)組return new int[0];}// 自定義比較器，實(shí)現(xiàn)大根堆Comparator<Integer> cmp = new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}};// 創(chuàng)建一個(gè)大小為 k 的大根堆，O(k*logk)PriorityQueue<Integer> pq = new PriorityQueue<>(k, cmp);for (int i = 0; i < k; i++) {pq.offer(arr[i]);}// 遍歷數(shù)組，如果元素小于堆頂元素，替換堆頂元素，并調(diào)整堆，O((N-k)logk)for (int i = k; i < arr.length; i++) {if (arr[i] < pq.peek()) {pq.poll();pq.offer(arr[i]);}}// 取出堆中的元素，存入數(shù)組，O(k*logk)int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = pq.poll();}return ret;}

5.2、堆排序

將序列從小到大排序：

• 方法1：創(chuàng)建小根堆，每次取堆頂，放入一個(gè)新的數(shù)組中。

空間復(fù)雜度：O(N)，創(chuàng)建了一個(gè)新數(shù)組存放結(jié)果。當(dāng)數(shù)據(jù)很多時(shí)，浪費(fèi)內(nèi)存。

時(shí)間復(fù)雜度：O(NlogN)。

• 方法2：創(chuàng)建大根堆，執(zhí)行 N-1 次循環(huán)，每次將堆頂最大元素與未排序的堆尾元素交換，交換后對未排序的部分進(jìn)行調(diào)整。

空間復(fù)雜度：O(1)

時(shí)間復(fù)雜度：O(NlogN)

????????初始狀態(tài)：

? ? ? ? 第一次交換，并調(diào)整：

? ? ? ? 第二次交換，并調(diào)整：

    // 堆排序public void sort() {for (int i = usedSize-1; i > 0; i--) {// 交換堆頂和最后一個(gè)未排序的元素swap(0, i);// 向下調(diào)整堆，元素 i-1 已排序shiftDown(0, i-1);}}