????在我們的計算機(jī)操作系統(tǒng)中，經(jīng)常使用到優(yōu)先隊列來存儲數(shù)據(jù)。我們計算機(jī)中的CPU按一定的調(diào)度算法從就緒隊列中選擇一個進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程。這個需求是很頻繁的。其實我們常說的優(yōu)先隊列就是最大最小堆。
????堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節(jié)點的元素都要大于等于其孩子，最小堆要求節(jié)點元素都小于等于其左右孩子，兩者對左右孩子的大小關(guān)系不做任何要求，其實很好理解。小編今天分享下有關(guān)最大堆的算法實現(xiàn)及對其時間復(fù)雜度做簡單分析。
????首先，最大堆的定義意味著最大元素就在堆的樹根。如果元素都是不相同的，樹根就保存著最大的元素。小編在算法實現(xiàn)上，采用了數(shù)組來實現(xiàn)最大堆【這里實現(xiàn)的是二叉樹堆】。
????我們先來看看這樣的一個數(shù)組：Array[6]={45,36,18,53,72,30}
? ? 一般來說，有兩種方式來實現(xiàn)最大堆的創(chuàng)建。包括自頂向下的建堆方式和自下向上的建堆方式。我們先來看第一種。
一、自頂向下
????從根結(jié)點開始，然后一個一個的把結(jié)點插入堆中。當(dāng)把一個新的結(jié)點插入堆中時，需要對結(jié)點進(jìn)行調(diào)整，以保證插入結(jié)點后的堆依然是大根堆。一起看看是如何通過插入的方式來建立一個最大堆的【按數(shù)組中的元素順序來插入，這里最大堆用數(shù)組heap[n]表示，且元素從1開始存放】。
????最終得到的堆中的元素順序為72、53、30、36、45、18。
? ? 使用自上而下建立二叉堆，那么插入每個節(jié)點都和樹的深度有關(guān)，并且都是不斷的把樹折半來實現(xiàn)插入，因此是典型的遞歸，而非疊加。其中樹的h =-1，第k層結(jié)點個數(shù)為
個(當(dāng)然最后一層結(jié)點個數(shù)可能小于
)。第k層的一個結(jié)點插入之后需要進(jìn)行的比較(移動)次數(shù)為k。于是總的比較(移動)次數(shù)為∑k*2*
(k = 0,1,2,...,h)?？梢郧蟮?/p>
????∑k*(k = 0,1,2,...,h)=(
-2)*(n+1)+2 = O(n*
)
? ? 因此這種插入方法的時間復(fù)雜度為O(n)。
二、自底向上
????除了通過插入的方法，我們還可以通過別的方法來構(gòu)建這個最大堆。先把a(bǔ)rray數(shù)組里的值賦值給heap[1]到heap[n]，這時得到的堆數(shù)組不是最大堆，是沒有經(jīng)過調(diào)整的，需要進(jìn)行調(diào)整。我們需要做的是從第一個非葉子結(jié)點開始進(jìn)行判斷該子樹是否滿足堆的性質(zhì)。如果滿足就繼續(xù)判斷下一個點。否則，如果子樹里面某個子結(jié)點有最大元素，則交換他們，并依次遞歸判斷其子樹是否仍滿足堆性質(zhì)。下圖第一個圖中的非葉子節(jié)點元素為18【數(shù)組長度為6，6/2=3獲得第一個非葉子節(jié)點在堆中位置heap[3]】，可以發(fā)現(xiàn)該子樹不是最大堆，要交換18和30兩個元素。接下來找到倒數(shù)第二個非葉子節(jié)點，其元素為36，發(fā)現(xiàn)子樹不是最大堆，調(diào)整。然后找到最后的根節(jié)點，發(fā)現(xiàn)子樹不滿足最大堆性質(zhì)，調(diào)整。最后得到的最大堆就是最后的圖所示。
????這個時候得到的最大堆元素排列為72、53、30、45、36、18。
????初始化建堆只需要對二叉樹的非葉子節(jié)點調(diào)用Adjust()函數(shù)，由下至上，由右至左選取非葉子節(jié)點來調(diào)用Adjust()函數(shù)。那么倒數(shù)第二層的最右邊的非葉子節(jié)點就是最后一個非葉子結(jié)點。
? ??如果僅從下面展示的代碼上直觀觀察，會得出構(gòu)造二叉堆的時間復(fù)雜度為O(n)的結(jié)果，這個結(jié)果是錯的，雖然該算法外層套一個n次循環(huán)，而內(nèi)層套一個分治策略下的
復(fù)雜度的循環(huán)，該思考方法犯了一個原則性錯誤，那就是構(gòu)建二叉堆是自下而上的構(gòu)建，每一層的最大縱深總是小于等于樹的深度的，因此，該問題是疊加問題，而非遞歸問題。
????假設(shè)高度為k，則從倒數(shù)第二層右邊的節(jié)點開始，這一層的節(jié)點都要執(zhí)行子節(jié)點比較然后交換（如果順序是對的就不用交換）；倒數(shù)第三層呢，則會選擇其子節(jié)點進(jìn)行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。如果交換了，那么又要選擇一支子樹進(jìn)行比較和交換；高層也是這樣逐漸遞歸。
????因此自底向上的建堆時間復(fù)雜度為O(n)。
????兩種方法得到的都是最大堆，接下來就是小編自己寫的代碼，截圖如下：
? ? 在代碼中，insert函數(shù)就是自頂向上的的方法。ArrToHeap函數(shù)使用的是用自底向上的調(diào)整方法。關(guān)于 最大堆代碼中的其它函數(shù)功能是怎樣的，小編已經(jīng)做了注釋。對于函數(shù)代碼的邏輯，這里小編就不分析了。核心邏輯就是上面的那幾幅圖。
????小編能力有限，可能會有些錯誤，歡迎指正。
