寶雞哪有有做網(wǎng)站的專業(yè)網(wǎng)絡(luò)推廣公司
文章目錄
目錄
文章目錄
前言
小堆:
大堆:?
二、使用步驟
1.創(chuàng)建二叉樹
2.修改為堆
3.向上調(diào)整
結(jié)果實現(xiàn)?
總結(jié)
前言
我們已經(jīng)知道了二叉樹的樣子,但是一般的二叉樹是沒有什么意義的,所以我們會使用一些特殊的二叉樹來進行實現(xiàn),而堆就為特殊的二叉樹來表示的。
一、堆是什么?
堆是一種特殊的二叉樹,由完全二叉樹來表示,分為小堆和大堆的表現(xiàn)形式,小堆的表現(xiàn)形式為父節(jié)點比孩子節(jié)點要小,下面的根節(jié)點同樣滿足這個條件,大堆與之相反,父節(jié)點要比孩子節(jié)點大,根節(jié)點同樣滿足條件。
小堆:
大堆:?
二、使用步驟
1.創(chuàng)建二叉樹
創(chuàng)建堆我們首先需要創(chuàng)建一個二叉樹,我們可以使用數(shù)組的形式來表示二叉樹,邏輯結(jié)構(gòu)上我們將數(shù)組看為二叉樹的形式,物理結(jié)構(gòu)上還為數(shù)組,我們現(xiàn)在需要將其修改為堆。
2.修改為堆
我們需要得知其的父節(jié)點個子節(jié)點,可以舉例為第一個節(jié)點為父節(jié)點下標(biāo)為0,子節(jié)點的下標(biāo)為1和2。當(dāng)父節(jié)點下標(biāo)為1時,子節(jié)點下標(biāo)3和4。由此可以推出公式,
父節(jié)點=(子節(jié)點-1)/2
子節(jié)點=父節(jié)點*2+1
通過這兩個公式我們就可以試著將二叉樹修改為堆。
3.向上調(diào)整
我們建造一個小堆要使父節(jié)點比子節(jié)點都要小,我們可以通過子節(jié)點和父節(jié)點進行對比,如果子節(jié)點更小的話就將其進行交換,我們可以通過公式由子節(jié)點來找到父節(jié)點來進行實現(xiàn),結(jié)束條件就為子節(jié)點小于或等于0時。
void Adjiustup(typedata* ps, int child)
{int parent = (child - 1) / 2;while (child > 0){if (ps[child] < ps[parent]){Swap(&ps[child], &ps[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
結(jié)果實現(xiàn)?
運行結(jié)果如圖所示,成功創(chuàng)建小堆,如果要創(chuàng)建大堆的話,只需要修改子節(jié)點和父節(jié)點的比較條件即可。
總結(jié)
一般的二叉樹是沒有什么意義的,這個堆我們可以根據(jù)其的特性進行一些有意義的事情,希望我的這篇文章對您有所幫助,如有錯誤,歡迎指出。