概念
優(yōu)先級隊列是啥？?
堆是啥？
優(yōu)先級隊列的底層運用到堆這種數(shù)據(jù)結(jié)構(gòu)
堆的特點：總是一棵完全二叉樹
大根堆：
每一棵樹的根結(jié)點總是比左右子節(jié)點大
小根堆：
每一棵樹的根結(jié)點的值總是比左右子節(jié)點小，不考慮左右子節(jié)點誰大誰小
堆的存儲
存儲方式采用層序遍歷的方式把二叉樹的元素一一放到數(shù)組里面
那數(shù)組可不可以存儲非完全二叉樹呢？答案是可以的，但是會有空間浪費的情況
像上面右邊圖，4的位置沒有存儲元素，這就是一種空間浪費
來手搓一個堆
回顧一下二叉樹里面性質(zhì)的第五點
如何將普通數(shù)組轉(zhuǎn)換成堆?
把下面數(shù)組的元素畫成堆
先畫成一棵普通的二叉樹
畫成大根堆
28<37，互換。最左邊子樹49>25>18，把49變成該樹的根結(jié)點，最右邊的樹65>34>19，也進行交換
調(diào)整第二層的樹，49>15>37，49作為根，而15<18<25，下方的樹得把25變成根
最上面一層的樹，65>49>27，65做根結(jié)點，而27<34，所以34還得作為該子樹的根結(jié)點
這就是一個大根堆了
總結(jié)：
1.從最后一棵子樹開始調(diào)整
2.在要變換的樹里面，從左右孩子里面找到最大的與根結(jié)點比較，大了就進行互換
3.如果能夠知道子樹根結(jié)點下標(biāo)，那么下一棵子樹就是當(dāng)前根結(jié)點下標(biāo)-1
4.一直調(diào)整到0下標(biāo)這個樹為止
先寫個初步的代碼
public class TestHeap {
private int[] elem;
public int usedSize;//記錄當(dāng)前堆當(dāng)中有效的數(shù)據(jù)個數(shù)
public TestHeap(){
this.elem = new int[10];
}
//存儲數(shù)組
public void initElem(int[] array){
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
問題
1.最后一棵子樹根結(jié)點下標(biāo)是多少
因為i = len-1，所以根結(jié)點index = (i-1)/2
public void createHeap(){
//usedSize-1相當(dāng)于最后一棵樹孩子結(jié)點的下標(biāo)i，再-1是為了求父結(jié)點
for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
siftDown(parent,usedSize);
}
}
2.每棵子樹調(diào)整完之后，結(jié)束的位置怎么定？也就是我要從哪里開始調(diào)整下一棵子樹？?
我們采用向下調(diào)整的方法（注意，雖然我們是從最后一顆樹往根結(jié)點方向調(diào)整，但是每一棵樹的處理我們還是采用從父結(jié)點到子節(jié)點的調(diào)整方法。為什么用不向上調(diào)整？后面我會說到。）
找到最后一個元素置為c，其根結(jié)點為p
調(diào)整完后不知道下面還有沒有元素要調(diào)整，所以c還得往下走?
此時c的坐標(biāo)是19 > 10了，所以可以停止了
private void siftDown(int parent, int len){
int child = 2 * parent + 1;
while(child < len){
//左右孩子比較大小
if(elem[child] < elem[child + 1]){
child = child + 1;
}
//走完上面的if，證明child下標(biāo)一定是左右兩個孩子最大值的下標(biāo)
}
}現(xiàn)在問題來了，寫到這里會發(fā)生數(shù)組越界，如果我的child移到9下標(biāo)這里，那這個if判斷elem[child] < elem[child+1] 這里的child+1 = 10 = usedSize，而這棵樹根本就沒有10這個下標(biāo)，造成了越界?
修改一下代碼
if(child+1<len && elem[child] < elem[child + 1]){
child = child + 1;
}后面就是比較孩子和父結(jié)點的代碼了
/**
* 向下調(diào)整
* @param parent
* @param len
*/
private void siftDown(int parent, int len){
int child = 2 * parent + 1;
while(child < len){
//左右孩子比較大小
if(child+1<len && elem[child] < elem[child + 1]){
child = child + 1;
}
//走完上面的if，證明child下標(biāo)一定是左右兩個孩子最大值的下標(biāo)
if(elem[child] > elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}else{
break;//不用比不用調(diào)了
}
}
}測試一下，沒有問題??
怎么計算這個堆的時間復(fù)雜度？
考慮最壞情況，就是滿二叉樹的情況
首先明確一點，最后一層結(jié)點時不進行調(diào)整的，一般是從倒數(shù)第二層結(jié)點開始調(diào)整的
設(shè)樹的高度是h
T(N) = (h-1)*2^0+(h-2)*2^1+(h-3)*2^2+......+2*2^(h-3)+1*2^(h-2)
怎么求這個等式？采用錯位相減
根據(jù)等比求和公式
T(n) = 2 ^ h - 1 - h
因為n=2^h-1? ? --> h = log(n+1)
代進去T(n) = n - log(n+1)
因為log(n+1)的圖長這樣，n越大越趨于一個常數(shù)
所以整個等式占支配地位的還得是n，所以T(N) ≈ n? -->時間復(fù)雜度：O(N)
堆的插入
如果插入的數(shù)值比較小
如果插入的數(shù)值比較大，那就得一層一層進行調(diào)整
這種調(diào)整叫做向上調(diào)整
public void swap(int i, int j){
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
public void push(int val){
if(isFull()){
elem = Arrays.copyOf(elem, 2*elem.length);
}
elem[usedSize] = val;
//向上調(diào)整
siftUp(usedSize);
usedSize++;
}
//判斷滿不滿
public boolean isFull(){
return usedSize == elem.length;
}
public void siftUp(int child){
int parent = (child - 1) / 2;
while(child>0){
if(elem[child] > elem[parent]){
swap(child,parent);
child = parent;
parent = (child - 1) / 2;
}else{
break;
}
}
}在測試?yán)锩姘?0push進去，沒有問題??
堆的插入的時間復(fù)雜度
因為最壞情況插入的元素是最大的，那這個元素最多也就向上調(diào)整到根節(jié)點的位置，也就是h
復(fù)雜度就是O(logN）?
欸那為什么不用向上調(diào)整來建堆呢？??
我們分析一下，拿這棵滿二叉樹來說，最底層有8個元素，已經(jīng)占了一半了，網(wǎng)上建堆得每個元素都遍歷一遍，時間復(fù)雜度太大了
?
?
堆的刪除
因為堆的刪除一定是刪除優(yōu)先級最高的值，所以一定是刪除大根堆的根結(jié)點
比如這個，我們要做的就是刪除65
第一步：把65（0下標(biāo)）與28（最后一個元素）進行交換
第二步：向下調(diào)整0下標(biāo)
public int pop(){
if(empty()){
throw new EmptyException("數(shù)組空了！");
}
int oldVal = elem[0];
swap(0,usedSize-1);
usedSize--;
siftDown(0,usedSize);
return oldVal;
}
public boolean empty(){
return usedSize == 0;
}測試一下，沒有問題??
習(xí)題：
選A（可以自己畫圖，反正就是層序遍歷畫樹）
選C
?
總共比較3次，左邊那個15的原本就是小根堆，所以就不用比較
PriorityQueue
Java集合框架提供了PriorityQueue的優(yōu)先級隊列
注意事項：
PriorityQueue<Student> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.offer(new Student("zhangsan",10));
priorityQueue1.offer(new Student("lisi",12));?1.PriorityQueue放入的元素必須能比較大小，否則會報出下面的錯誤?
2.不能插入null對象，否則會報出下面的錯誤
PriorityQueue<Student> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.offer(null);?
3.沒有容量限制，可以插入任意多個元素，內(nèi)部會自動擴容
4.插入和刪除都是O(logn)?
5.使用了最小堆的數(shù)據(jù)結(jié)構(gòu)，所以每次獲取的元素都是最小的元素
oj練習(xí)
面試題 17.14. 最小K個數(shù) - 力扣（LeetCode）
設(shè)計一個算法，找出數(shù)組中最小的k個數(shù)。以任意順序返回這k個數(shù)均可。
示例：
輸入： arr = [1,3,5,7,2,4,6,8], k = 4 輸出： [1,2,3,4]
提示：
0 <= len(arr) <= 1000000 <= k <= min(100000, len(arr))
方法一：
建立最小堆，把堆頂k個元素輸出出來就行了
代碼
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//向上調(diào)整 O(logN)
for (int i = 0; i < array.length; i++) {
priorityQueue.offer(array[i]);
}
int[] ret = new int[k];
//k*logN
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
雖然通過了，但是時間復(fù)雜度有點大?
方法二：
1.建立大根堆，大小為k，比如我們可以拿前三個元素來建一個大根堆
2.從第k+1個元素開始比較，如果比堆頂元素小，則入堆。當(dāng)前的堆頂元素(較大的)就舍棄掉，因為已經(jīng)不符合我對前k個最小的元素的要求了
遍歷完整個大根堆長這樣
問題來了，PriorityQueue是默認(rèn)采用小根堆的底層，那我們要怎么讓它采用大根堆呢
PriorityQueue源碼里面的有一個compare函數(shù)
這個函數(shù)外層是compareTo函數(shù)
這兩個函數(shù)結(jié)合一下，把小的放在前面，大的放在后面，所以實現(xiàn)了小根堆的底層
我們可以重寫PriorityQueue里面的compare函數(shù)，把大的放在前面
class Imp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}整個的代碼（上面的重寫可以扔到匿名內(nèi)部類里面）
public static int[] smallestK(int[] array, int k) {
int[] ret = new int[k];
if(array == null || k <= 0) {
return ret;
}
//匿名內(nèi)部類
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
//1、建立大小為k的大根堆 O(K*logK)
for (int i = 0; i < k; i++) {
priorityQueue.offer(array[i]);
}
//2、遍歷剩下的元素 (N-K)*logK
// (K*logK) + N*logK - K*logK = N*logK -->時間復(fù)雜度
for (int i = k; i < array.length; i++) {
int top = priorityQueue.peek();//27
if(array[i] < top) {
priorityQueue.poll();
priorityQueue.offer(array[i]);
}
}
//下面這個不能算topK的復(fù)雜度 這個地方是整理數(shù)據(jù)
//k*logK
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}?
別看力扣上面的通過時間，我們要自行分析時間復(fù)雜度?
拓展：Comparable接口和Comparator接口
使用Comparable意味著這個類只能有一種比較規(guī)則（你拿你自己和別人家的孩子比成績）
一個類只能實現(xiàn)一次Comparable，這種寫法對類的侵入性比較強
使用Comparator意味著可以有多重比較規(guī)則（你媽拿你和別人家孩子對比的時候，可以比較學(xué)習(xí)成績，聽話程度，做不做家務(wù)）
這里的compareTo和compare方法就是回調(diào)函數(shù)
回調(diào)函數(shù)是一種特殊的函數(shù)，它作為參數(shù)傳遞給另一個函數(shù)，并在被調(diào)用函數(shù)執(zhí)行完畢后被調(diào)用
堆排序
把這個數(shù)組從小到大排序，需要建立大根堆
再把這棵樹放到堆底，這樣最大的元素就有序了
再按照大根堆進行排序（已經(jīng)有序的元素就不管了），把最大元素49放到堆頂，然后再和堆第的15交換
以此類推，設(shè)置一個堆底end，每次拿0下標(biāo)的元素和它交換，交換完end--文章來源：http://www.zghlxwxcb.cn/news/detail-714669.html
public void heapSort(){
int end = usedSize-1;
while(end>0){
swap(0,end);
siftDown(0,end);
end--;
}
}時間復(fù)雜度O(N*logN)文章來源地址http://www.zghlxwxcb.cn/news/detail-714669.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：優(yōu)先級隊列（堆）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
