第Java數(shù)據(jù)結(jié)構(gòu)中堆的向下和向上調(diào)整解析目錄一、關(guān)于堆1.堆的概念2.堆的性質(zhì)3.堆的存儲方式二、堆的創(chuàng)建1.堆向下調(diào)整2.堆的創(chuàng)建三、向上調(diào)整

一、關(guān)于堆

JDK1.8中的PriortyQueue（優(yōu)先級隊(duì)列）底層使用了堆的數(shù)據(jù)結(jié)構(gòu)，而堆實(shí)際就是在完全二叉樹的基礎(chǔ)之上進(jìn)行了一些元素的調(diào)整。

1.堆的概念

堆有最大堆和最小堆之分。

最大（最?。┒咽且豢妹恳粋€節(jié)點(diǎn)的元素都不小于（大于）其孩子（如果存在）的元素的樹。大堆是一棵完全二叉樹，同時也是一棵最大樹。小堆是一棵完全二叉樹，同時也是一棵最小樹。

注意：堆中的任一子樹也是堆，即大堆的子樹也都是大堆，小堆亦是。

2.堆的性質(zhì)

堆中某個結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值

堆總是一顆完全二叉樹

3.堆的存儲方式

由堆的概念可知，堆是一顆完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲。

注意：對于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲，因?yàn)闉榱四軌蜻€原二叉樹，空間中必須要能夠存儲空結(jié)點(diǎn)，就會導(dǎo)致空間利用率比較低

二、堆的創(chuàng)建

1.堆向下調(diào)整

對于給出的一個數(shù)據(jù)，如何將其創(chuàng)建為堆呢？例如下圖：

仔細(xì)觀察上圖后發(fā)現(xiàn)：根結(jié)點(diǎn)的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根結(jié)點(diǎn)向下調(diào)整好即可。

以小堆為例：

1.讓parent標(biāo)記需要調(diào)整的結(jié)點(diǎn)，child標(biāo)記parent的左孩子（注意：parent如果有孩子一定是先有左孩子）

2.如果parent的左孩子存在，即childsize，進(jìn)行如下操作，直到parent的左孩子不存在

parent右孩子是否存在，如果存在則找出左右孩子中較小的孩子，使用child進(jìn)行標(biāo)記

將parent與較小的孩子（也就是此時的child）比較，如果：

parent小于較小的孩子child，這個結(jié)點(diǎn)已經(jīng)調(diào)整

否則：將parent與child進(jìn)行交換，交換成功后，這時parent中大的元素已經(jīng)向下移動，可能會導(dǎo)致子樹不滿足堆的特性，就需要繼續(xù)向下調(diào)整，即parent=child,child=parent*2+1,然后循環(huán)起來

圖解如下：

代碼實(shí)現(xiàn)：

privatevoidshiftDown(intparent){

//默認(rèn)讓child先標(biāo)記左孩子---因?yàn)椋簆arent可能有左沒有右

intchild=parent*2+1;

//while循環(huán)條件可以保證：parent的左孩子一定存在

//但是不能保證parent的右孩子是否存在

while(childsize){

//1.找到左右孩子中較小的孩子

if(child+1sizearray[child+1]array[child]){

child+=1;

//2.較小的孩子已經(jīng)找到了

//檢測雙親和孩子之間是否滿足堆的特性

if(array[parent]array[child]){

swap(parent,child);

//大的雙親往下走，可能會導(dǎo)致子樹又不滿足堆的特性

//因此需要繼續(xù)往下調(diào)整

parent=child;

child=parent*2+1;

}else{

//以parent為根的二叉樹已經(jīng)是堆了

return;

注意：在調(diào)整以parent為根的二叉樹時，必須要滿足parent的左子樹和右子樹已經(jīng)是堆了才可以向下調(diào)整。

時間復(fù)雜度（看最壞的情況）：從根一路比較到葉子，比較的次數(shù)為完全二叉樹的高度，即時間復(fù)雜度為O(logn)。

2.堆的創(chuàng)建

向下調(diào)整的情況只能針對左右子樹已經(jīng)是堆了才可以調(diào)整，那假如根結(jié)點(diǎn)的左右子樹不滿足堆的特性，又該如何調(diào)整呢？例如下圖：

我們要從3這里的位置開始向下調(diào)整，然后逐漸向前依次向上調(diào)整

3這個位置很特殊，他是二叉樹倒數(shù)第一個非葉子結(jié)點(diǎn)

步驟：

1.找到倒數(shù)第一個非葉子結(jié)點(diǎn)

2.從該結(jié)點(diǎn)位置開始往前一直到根結(jié)點(diǎn)，每遇到一個結(jié)點(diǎn)就使用向下調(diào)整

代碼實(shí)現(xiàn)：

publicstaticvoidcreateHeap(int[]array){

//注意：倒數(shù)第一個非葉子節(jié)點(diǎn)剛好是最后一個節(jié)點(diǎn)的雙親

//最后一個結(jié)點(diǎn)的編號是size-1，倒數(shù)第一個非葉子節(jié)點(diǎn)的下標(biāo)為（size-1-1）/2

intlastLeafParent=(size-2)/2;

//從倒數(shù)第一個非葉子節(jié)點(diǎn)位置開始，一直到根節(jié)點(diǎn)的位置，使用向下調(diào)整

for(introot=lastLeafParent;rootroot--){

shiftDown(root);

建堆的時間復(fù)雜度：

因?yàn)槎咽峭耆鏄?，滿二叉樹也是完全二叉樹，為了簡化計(jì)算，此處使用滿二叉樹來證明：

假設(shè)滿二叉樹高度h

第一層：20個結(jié)點(diǎn)，需要向下移動h-1層

第二層：21個結(jié)點(diǎn)，需要向下移動h-2層

第二層：22個結(jié)點(diǎn)，需要向下移動h-3層

…以此類推就可以求出所有的移動步數(shù)：每一層結(jié)點(diǎn)數(shù)與對應(yīng)移動層數(shù)相乘再整體相加

然后再利用一定的數(shù)學(xué)巧妙運(yùn)算（此處省略那些繁瑣的數(shù)學(xué)公式，屬實(shí)是頭大）就得出T(n)=n=log(n+1)≈n

因此：建堆的時間復(fù)雜度為O(N)。

三、向上調(diào)整

向上調(diào)整主要的應(yīng)用場景就是在堆的插入

堆的插入總共需要兩個步驟：

1.先將元素插入到堆的末尾，即最后一個孩子之后

2.插入后如果堆的性質(zhì)遭到破壞，將最后新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)

代碼實(shí)現(xiàn)：

privatevoidshiftUp(intchild){

intparent=(child-1)/2;