---

優(yōu)先級隊列

前面介紹過隊列，隊列是一種先進先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，但有些情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級，一般出隊列時，可能需要優(yōu)先級高的元素先出隊列，該種場景下，使用隊列顯然不合適，比如：在手機上玩游戲的時候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進來的電話；初中那會班主任排座位時可能會讓成績好的同學(xué)先挑座位。在這種情況下，數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)。

堆

優(yōu)先級隊列是一種概念的數(shù)據(jù)結(jié)構(gòu)，我們使用堆這種具體的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)它。

堆的概念

堆是一棵以數(shù)組方式存儲的完全二叉樹。
存儲方式按照層序遍歷的方式存儲。

堆又分為小根堆，大根堆兩種：
大根堆是指所有的節(jié)點值比其左右節(jié)點值都大（左右節(jié)點在的情況下）。
大根堆的根節(jié)點是最大值
小根堆是指所有的節(jié)點指比其左右節(jié)點值都小（左右節(jié)點在的情況下）。
小根堆的根節(jié)點是最小值

堆的模擬實現(xiàn)

我們以大根堆舉例：
實現(xiàn)的方法與屬性：

public class PriorityQueue {public int[] elem;public int usedSize;//初始化長度為10的數(shù)組public PriorityQueue() {elem = new int[10];}//創(chuàng)建建堆public void createHeap(int[] array) {}private void shiftDown(int root,int len) {}// 入堆：仍然要保持是大根堆public void push(int val) {}private void shiftUp(int child) {}//判斷堆是否滿public boolean isFull() {}//每次刪除的都是優(yōu)先級高的元素,刪除后任是大根堆public void pollHeap() {}//判斷堆是否為空public boolean isEmpty() {}// 獲取堆頂元素public int peekHeap() {}
}

創(chuàng)建堆

創(chuàng)建堆的方式有兩種，一種是向上調(diào)整，向下調(diào)整。
我們依次介紹：
向下調(diào)整：根據(jù)一組數(shù)據(jù)創(chuàng)建成一個大根堆，以{1，5，3，8，7，6}舉例：

 所以向下調(diào)整的含義即每一棵子樹均從根節(jié)點開始向下比較。

實現(xiàn)思想：

1. createHeap思路：

先將數(shù)組拷貝進成員數(shù)組中（注意看長度是否夠）。
我們從最后一棵子樹的根節(jié)點開始調(diào)用shiftDown方法向上一棵一棵樹的調(diào)整為大根堆。
2. shiftDown思路：

將當前傳入的根節(jié)點與他的孩子節(jié)點將最大值選出作為根。
然后將根變成孩子節(jié)點再次調(diào)整。
注意挑選最大值的時候要判斷不能讓下標越界。

public void createHeap(int[] array) {if(elem.length < array.length){elem = Arrays.copyOf(elem, elem.length * 2);}for (int i = 0; i < array.length; i++){elem[i] = array[i];usedSize++;}for (int root = (usedSize -1 -1) / 2; root >= 0 ; root--) {siftDown(root,usedSize);}}private void siftDown(int root,int len) {int child = root * 2 + 1;while (child < len){//尋找孩子節(jié)點的大值if(child + 1 < len && elem[child] < elem[child + 1]){child++;}if(elem[root] < elem[child]){swap(elem,root,child);root = child;child = root * 2 + 1;}else {break;}}}//交換函數(shù)private void swap(int[] array,int x,int y){int tmp = array[x];array[x] = array[y];array[y] = tmp;}

向上調(diào)整：
向上調(diào)整的思路即以入堆的方式，將每一個元素依次插入堆中。

 我們從最后一棵節(jié)點開始于其子樹的根節(jié)點比較，這個向上比較的過程，我們稱為向上調(diào)整。

代碼實現(xiàn)：

public class Test {public static void main(String[] args) {int [] array = {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap = new TestHeap();for (int i = 0; i < array.length; i++) {testHeap.push(array[i]);}}
}

 具體的入堆代碼，看下面。

入堆

代碼思路：

1. 先判斷堆是否已經(jīng)滿了，滿了要擴容。
2. 在堆最后存入該元素，然后與父親節(jié)點相比較，比父親節(jié)點大就交換，直到到根節(jié)點或者比父親節(jié)點小為止。

public void push(int val) {if(isFull()){elem = Arrays.copyOf(elem, elem.length*2);}elem[usedSize] = val;siftUp(usedSize);usedSize++;}private void siftUp(int child) {int parent = (child - 1) / 2;while(parent >= 0) {if (elem[parent] < elem[child]) {swap(elem, parent, child);child = parent;parent = (child - 1) / 2;}else {break;}}}

判滿

public boolean isFull() {return usedSize == elem.length;}

刪除

實現(xiàn)思想：

1. 先判斷堆是否為空，為空直拋空指針異常。
2. 我們先將堆頂和堆尾交換，然后向下調(diào)整一次。
3. usedSize減1。

public void pollHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}swap(elem,0,usedSize-1);siftDown(0,usedSize);usedSize--;}

判空

public boolean isEmpty() {return usedSize == 0;}

獲取棧頂元素

如果堆為空，拋空指針異常，沒有直接返回堆頂元素。

public int peekHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}return elem[0];}

創(chuàng)建堆兩種方式的時間復(fù)雜度

向下調(diào)整的時間復(fù)雜度為O（N）：

當計算復(fù)雜度時，只計算替換次數(shù)即可，不需要計算每次替換中語句的執(zhí)行數(shù)目，因為到最后計算時，前面的系數(shù)均會變?yōu)?.
向上調(diào)整的時間復(fù)雜度為O(N*logN)：

堆排序

假設(shè)我們要將一組數(shù)據(jù)在一個數(shù)組中從小到大排序，那我們要創(chuàng)建大根堆，還是小根堆？
如果要創(chuàng)建小根堆，我們只能保證堆頂元素為最小值，但是不能保證，左邊的元素比右邊的元素大，這不是小根堆的特性。
所以我們要創(chuàng)建大根堆

public void heapsort(){
//此方法是在創(chuàng)建大根堆之后的堆排序方法int end = Usedsize-1;while(end>0){swap(elem,0,end);siftDown(0,end);end--; }
}

java提供的PriorityQueue類

基本的屬性

1. DEFAULT_INITIAL_CAPACITY 為申請初始化空間大小的默認值
2. queue為底層使用的數(shù)組
3. size指數(shù)組中有效元素的個數(shù)
4. comparator指類使用的比較器

關(guān)于PriorityQueue類的三個構(gòu)造方法

這三個構(gòu)造方法均調(diào)用了自己的第四個構(gòu)造方法

所以我們直接看第四個構(gòu)造方法實現(xiàn)邏輯：如果申請的空間大小小于1，則直接報異常，當大于等于1時，為優(yōu)先級隊列申請第一個參數(shù)數(shù)值大小的空間，并采用第二個參數(shù)的比較器。

關(guān)于PriorityQueue類中，入堆方法是怎樣實現(xiàn)的？

PriorityQueue注意事項

1. PriorityQueue中放置的元素必須是可以比較的，即實現(xiàn)了comparable接口的類,否則會報ClassCastException異常。
2. 不能插入null對象，否則會報NullPointerException異常。
3. 沒有容量限制，可以插入任意多個元素，其內(nèi)部可以自動擴容。

堆的一個oj題

Topk問題，最小的k個數(shù)
這個題有三種做法：

1. 直接進行整體堆排序。

2. 直接建立一個小根堆，然后依次出堆頂元素，再調(diào)整

3. 把前k個元素創(chuàng)建為大根堆，遍歷剩下的N-K個元素，和棧頂元素比較，如果比棧頂元素小，則刪除棧頂元素，將此元素入堆。
   此種算法的時間復(fù)雜度為：前k個元素創(chuàng)建一個大根堆的時間復(fù)雜度加上后面N-k個元素進行入堆操作的時間復(fù)雜度==klogk+(N-k)*logk == Nlogk
   采用第三種做法：

class Clmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
class Solution {public int[] smallestK(int[] arr, int k) {int [] ret = new int[k];if(arr ==null||k==0){return ret;}PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(k,new Clmp());//我們需要創(chuàng)建一個大根堆//將前k個元素插入到優(yōu)先級隊列中去for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}
//然后遍歷剩余的元素for (int i = k; i <arr.length ; i++) {if(arr[i] < priorityQueue.peek()) {//則將兩者的值進行交換priorityQueue.poll();priorityQueue.offer(arr[i]);}}ret = new int[k];for (int i = 0; i < k; i++) {ret[i]  = priorityQueue.poll();}return ret;}
}