文章目錄

前言

我們已經(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ù)其的特性進行一些有意義的事情，希望我的這篇文章對您有所幫助，如有錯誤，歡迎指出。