目錄

滿二叉樹與完全二叉樹高度h和樹中節(jié)點(diǎn)個數(shù)N的關(guān)系

向上調(diào)整算法：

介紹：

復(fù)雜度推導(dǎo)：

向下調(diào)整算法：

介紹：

復(fù)雜度推導(dǎo)：

向上調(diào)整建堆：

介紹：

復(fù)雜度推導(dǎo)：

向下調(diào)整建堆：

介紹：

復(fù)雜度推導(dǎo)：

---

滿二叉樹與完全二叉樹高度h和樹中節(jié)點(diǎn)個數(shù)N的關(guān)系

向上調(diào)整算法：

介紹：

函數(shù)功能：將堆通過向上調(diào)整算法使堆成為小堆（父親<孩子）或大堆（父親>孩子），堆內(nèi)父親=（孩子-1）/2。只要孩子還在堆范圍內(nèi)，就不斷判斷孩子與父親的關(guān)系。若想設(shè)置小堆，則孩子<父親就執(zhí)行交換；若想設(shè)置大堆，則孩子>父親就執(zhí)行交換。

函數(shù)參數(shù)：HeapDataType * a—>堆內(nèi)數(shù)據(jù)類型首元素的指針? int child—>堆底元素（孩子）

函數(shù)返回值：無

void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

復(fù)雜度推導(dǎo)：

一次向上調(diào)整最多調(diào)整高度次數(shù)，根據(jù)滿二叉樹h=log(N+1)，完全二叉樹h=log(N)+1，而時間復(fù)雜度計算的是最大情況的數(shù)量級，所以一次向上調(diào)整的復(fù)雜度為O(logN)

---

向下調(diào)整算法：

介紹：

函數(shù)功能：將堆通過向下調(diào)整算法使堆成為小堆（父親<孩子）或大堆（父親>孩子），使用假設(shè)法先假定要交換的元素為左孩子，child=parent*2+1，若右孩子>左孩子，則需交換的元素為parent*2+1+1。只要孩子還在堆范圍內(nèi)，就不斷判斷孩子與父親的關(guān)系。若想設(shè)置小堆，則孩子<父親就執(zhí)行交換；若想設(shè)置大堆，則孩子>父親就執(zhí)行交換。

函數(shù)參數(shù)：HeapDataType * a—>堆內(nèi)數(shù)據(jù)類型首元素的指針? int n —>堆內(nèi)元素個數(shù)? ? ? ? ? int parent—>堆頂元素（父親）

函數(shù)返回值：無

void Adjustdown(HeapDataType* a, int n, int parent)
{size_t child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

復(fù)雜度推導(dǎo)：

一次向下調(diào)整最多調(diào)整高度次數(shù)，根據(jù)滿二叉樹h=log(N+1)，完全二叉樹h=log(N)+1，而時間復(fù)雜度計算的是最大情況的數(shù)量級，所以一次向下調(diào)整的復(fù)雜度為O(logN)

---

向上調(diào)整建堆：

介紹：

前提：上幾層都是堆

先將數(shù)組內(nèi)所有元素插入堆結(jié)構(gòu)內(nèi)，再從第一個元素到最后一個元素進(jìn)行遍歷，對每個元素使用向上調(diào)整算法，使堆結(jié)構(gòu)成為大堆/小堆

復(fù)雜度推導(dǎo)：

---

向下調(diào)整建堆：

介紹：

前提：左右子樹都是堆

先將數(shù)組內(nèi)所有元素插入堆結(jié)構(gòu)內(nèi)，再從最后一個父親的位置到第一個父親的位置進(jìn)行遍歷，對每個元素使用向下調(diào)整算法，使堆結(jié)構(gòu)成為大堆/小堆

復(fù)雜度推導(dǎo)：