??優(yōu)先級(jí)隊(duì)列
?????優(yōu)先級(jí)隊(duì)列的概念
前面介紹過隊(duì)列，隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，但有些情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級(jí)，一般出隊(duì)列時(shí)，可能需要優(yōu)先級(jí)高的元素先出隊(duì)列，該中場(chǎng)景下，使用隊(duì)列顯然不合適。
比如：在手機(jī)上玩游戲的時(shí)候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話；初中那會(huì)班主任排座位時(shí)可能會(huì)讓成績好的同學(xué)先挑座位。
在這種情況下，數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作，一個(gè)是返回最高優(yōu)先級(jí)對(duì)象，一個(gè)是添加新的對(duì)象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級(jí)隊(duì)列(Priority Queue)。
??堆的由來
為了模擬實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的模擬實(shí)現(xiàn)，JDK1.8中的PriorityQueue底層使用了堆這種數(shù)據(jù)結(jié)構(gòu)，而堆實(shí)際就是在完全二叉樹的基礎(chǔ)上進(jìn)行了一些調(diào)整。
?????堆的概念
如果有一個(gè)關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ) 在一個(gè)一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為 小堆(或大
堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
?????堆的性質(zhì)
-
堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
-
堆總是一棵完全二叉樹。
?????堆的存儲(chǔ)方式
從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲(chǔ)
注意：對(duì)于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲(chǔ)，因?yàn)闉榱四軌蜻€原二叉樹，空間中必須要存儲(chǔ)空節(jié)點(diǎn)，就會(huì)導(dǎo)致空間利用率比較低
將元素存儲(chǔ)到數(shù)組中后，可以根據(jù)二叉樹章節(jié)的性質(zhì)5對(duì)樹進(jìn)行還原。假設(shè)i為節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則有：
-
如果i為0，則i表示的節(jié)點(diǎn)為根節(jié)點(diǎn)，否則i節(jié)點(diǎn)的雙親節(jié)點(diǎn)為 (i - 1)/2
-
如果2 * i + 1 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i + 1，否則沒有左孩子
-
如果2 * i + 2 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的右孩子下標(biāo)為2 * i + 2，否則沒有右孩子
??堆的創(chuàng)建
?????堆向下調(diào)整
對(duì)于集合{ 27,15,19,18,28,34,65,49,25,37 }中的數(shù)據(jù)，如果將其創(chuàng)建成堆呢？
仔細(xì)觀察上圖后發(fā)現(xiàn)：根節(jié)點(diǎn)的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根節(jié)點(diǎn)向下調(diào)整好即可。
向下過程(以小堆為例)：
- 讓parent標(biāo)記需要調(diào)整的節(jié)點(diǎn)，child標(biāo)記parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
- 如果parent的左孩子存在，即:child < size， 進(jìn)行以下操作，直到parent的左孩子不存在
parent右孩子是否存在，存在找到左右孩子中最小的孩子，讓child進(jìn)行標(biāo)
將parent與較小的孩子child比較，如果
- parent小于較小的孩子child，調(diào)整結(jié)束
- 否則：交換parent與較小的孩子child，交換完成之后，parent中大的元素向下移動(dòng)，可能導(dǎo)致子樹不滿足對(duì)的性質(zhì)，因此需要繼續(xù)向下調(diào)整
即parent = child；child = parent*2+1; 然后繼續(xù)2。
大堆實(shí)現(xiàn)與其類似
?????代碼實(shí)現(xiàn)
public class MyHeap {
public void shiftDown(int[] array, int parent) {
// child先標(biāo)記parent的左孩子，因?yàn)閜arent可能右左沒有右
int child = 2*parent + 1;
int size = array.length;
while(child < size ) {
// 如果右孩子存在，找到左右孩子中較小的孩子,用child進(jìn)行標(biāo)記
if(child + 1 < size) {
if(array[child + 1] < array[child]) {
child = child + 1;
}
}
// 如果最小的孩子比其父親還小，說明該結(jié)構(gòu)沒有滿足堆的特性，進(jìn)行交換
if(array[child] < array[parent]) {
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
} else {
//滿足就退出循環(huán)
break;
}
// parent中大的元素往下移動(dòng)，可能會(huì)造成子樹不滿足堆的性質(zhì)，因此需要繼續(xù)向下調(diào)整
parent = child;
child = 2*parent + 1;
}
}
}
??代碼測(cè)試結(jié)果展示
測(cè)試代碼
public class TestMain {
public static void main(String[] args) {
MyHeap myHeap = new MyHeap();
int[] array = {27,15,19,18,28,34,65,49,25,37};
System.out.println("調(diào)整前：");
for(int i = 0; i < array.length ; i++) {
System.out.print(array[i] + " ");
}
for(int parent = (array.length-2)/2 ; parent >= 0; parent --) {
myHeap.shiftDown(array, parent);
}
System.out.println();
System.out.println("調(diào)整后：");
for(int i = 0; i < array.length ; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
測(cè)試結(jié)果
注意：在調(diào)整以parent為根的二叉樹時(shí)，必須要滿足parent的左子樹和右子樹已經(jīng)是堆了才可以向下調(diào)整。
時(shí)間復(fù)雜度分析：
最壞的情況即圖示的情況，從根一路比較到葉子，比較的次數(shù)為完全二叉樹的高度，即時(shí)間復(fù)雜度為
??建堆的時(shí)間復(fù)雜度
對(duì)于普通的序列{ 1,5,3,8,7,6 }，我們需要建立大堆，即根節(jié)點(diǎn)的左右子樹不滿足堆的特性，又該如何調(diào)整呢？
做法如下：
找倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)，從該節(jié)點(diǎn)位置開始往前一直到根節(jié)點(diǎn)，遇到一個(gè)節(jié)點(diǎn)，應(yīng)用向下調(diào)整
for(int parent = (array.length-2)/2 ; parent >= 0; parent --) {
myHeap.bigDown(array, parent);
}
那么時(shí)間復(fù)雜度又為多少呢？
因?yàn)槎咽峭耆鏄?，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時(shí)間復(fù)雜度本來看的就是近似值，多幾個(gè)節(jié)點(diǎn)不影響最終結(jié)果)：
因此：建堆的時(shí)間復(fù)雜度為O(N)文章來源：http://www.zghlxwxcb.cn/news/detail-695170.html
?總結(jié)
關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】 優(yōu)先級(jí)隊(duì)列(堆)與堆的建立》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評(píng)指正，如果文章對(duì)您有幫助或者覺得作者寫的還不錯(cuò)可以點(diǎn)一下關(guān)注，點(diǎn)贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-695170.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 優(yōu)先級(jí)隊(duì)列(堆)與堆的建立的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
