💬 歡迎討論：在閱讀過程中有任何疑問，歡迎在評論區留言，我們一起交流學習！
👍 點贊、收藏與分享：如果你覺得這篇文章對你有幫助，記得點贊、收藏，并分享給更多對數據結構感興趣的朋友

前言

堆是一種基于完全二叉樹的數據結構，通常分為最大堆（父節點值≥子節點）和最小堆（父節點值≤子節點）。由于完全二叉樹的特性，堆可以用數組高效存儲，通過索引關系快速定位父子節點。

---

1. 堆的概念與結構

如果有?個關鍵碼的集合，把它的所有元素按完全?叉樹的順序存儲?式存儲，在?個?維數組中，并滿?： K = { k 0 , k 1 , k 2 , . . . , k n ? 1 } K=\{ k_0,k_1,k_2,...,k_{n-1} \} K={k0?,k1?,k2?,...,kn?1?}，i = 0、1、2...，則稱為?堆(或?堆)。將根結點最?的堆叫做最?堆或?根堆，根結點最?的堆叫做最?堆或?根堆。

---

1.2 堆的重要性質

對于具有n個結點的完全二叉樹，如果按照從上至下、從左至右的數組順序對所有結點從0開始編號，對于序號為i的結點有：

1. 若i > 0，i位置結點的雙親序號為：（i - 1）/2; 當i為0時，i為根結點。
2. 若2i + 1 < n，左孩子序號：2i + 1；如果2i + 1 >=n，則無左孩子
3. 若2i + 2 < n，左孩子序號：2i + 2；如果2i + 2 >=n，則無右孩子

---

2. 堆的實現

原碼自取gitee

現在我們知道，完全二叉樹的順序結構就是堆，顧名思義，堆就是用順序表（數組）實現的。

Heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;//堆int size;//堆的大小int capacity;//堆的容量
}HP;
//堆的初始化
void HeapInit(HP* php);
// 堆的銷毀
void HeapDestory(HP* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的刪除
void HeapPop(HP* php);
// 取堆頂的數據
HPDataType HeapTop(HP* php);
// 堆的數據個數
int HeapSize(HP* php);
// 堆的判空
int HeapEmpty(HP* php);
//向下調整
void AdjustDown(HPDataType* a, int n, int parent);
//向上調整
void AdjustUp(HPDataType* a, int child);
//交換
void swap(HPDataType* p1, HPDataType* p2);

聲明：本文以實現小堆為例，如需實現大堆，修改小堆調整算法的條件即可，這里不過多贅述。

---

2.1 堆的插入+向上調整算法

2.1.1 向上調整算法

該算法輔助實現堆的插入

將新數據插入到數組的尾上，再進行向上調整算法，直到滿足堆。

仔細觀察這個圖解，不難發現：從某個結點出發，與其父親比較，如果小于他的父親，就交換位置；如果大于或等于就不動，調整結束。

void AdjustUp(HPDataType* 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;}}
}

---

2.1.2 堆的插入

• 先將元素插?到堆的末尾,即最后?個孩?之后
• 插?之后如果堆的性質遭到破壞，將新插?結點順著其雙雙親往上調整到合適位置即可

void HeapPush(HP* php, HPDataType x)
{assert(php);//若空間不足，則擴容if (php->size == php->capacity) {HPDataType* ptr = realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (ptr == NULL) {perror("realloc fail");exit(-1);}php->a = ptr;php->capacity *= 2;}php->a[php->size] = x;AdjustUp(php->a, php->size);php->size++;
}

---

2.2 堆的刪除+向下調整算法

2.2.1 向下調整算法

該算法輔助實現堆的刪除

現在我們給出一個數組，邏輯上看做一顆完全二叉樹。我們通過從根節點開始的向下調整算法可以把它調整成一個小堆。向下調整算法有一個前提：左右子樹必須是一個堆，才能調整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

仔細觀察這個圖解，不難發現：從根結點出發，與其較小的孩子比較，如果小于這個孩子，就交換位置；如果大于或等于就不動，調整結束。

代碼核心：

1. 父親與孩子的下標關系：child=2*parent + 1
2. 孩子的下標小于n，避免數組越界訪問

void AdjustDown(HPDataType* a,int n,int parent)
{int child = 2 * parent + 1;while (child < n) {// 假設法，選出左右孩?中?的那個孩?if (a[child] < a[child + 1] && child + 1 < n){child++;}if (a[parent] < a[child]) {swap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1;}else break;}
}

---

2.2.2 堆的刪除

刪除時需注意判斷堆是否為非空，若對空堆進行刪除，必然出錯。

• 將堆頂元素與堆中最后?個元素進?交換
• 刪除堆中最后?個元素
• 將堆頂元素向下調整到滿?堆特性為?
  

void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));swap(php->a,&php->a[php->size-1]);php->size--;AdjustDown(php->a,php->size, 0);
}

---

其余的初始化、銷毀、判空等等，非常簡單，都是老套路了，這里留給讀者自己發揮。
在我過去的一些文章都有類似的詳解（順序表、鏈表、棧、隊列）。大家可以照貓畫虎。

傳送門呈上~
【初探數據結構】線性表———順序表的詳解和實現
【初探數據結構】線性表————鏈表（一）（單鏈表的實現）
【初探數據結構】線性表——鏈表（二）帶頭雙向循環鏈表（詳解與實現）
【初探數據結構】線性表——棧與隊列（代碼實現與詳解）

---

3. 復雜度分析（向上調整與向下調整）

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，為了簡化證明，此出以滿二叉樹為研究對象。(時間復雜度本來看的就是近似值，多幾個節點不影響最終結果)

---

3.1 向下調整時間復雜度（$O（N）$）

最壞的情況是什么呢？
就是樹的每個結點全部都要進行一次調整堆底。
設樹的高度為h
我們需要計算的是向下移動的總次數T(n)

分析：
第1層，$2^0$個結點，需要向下移動h-1層
第2層，$2^1$個結點，需要向下移動h-2層
第3層，$2^2$個結點，需要向下移動h-3層
第4層，$2^3$個結點，需要向下移動h-4層
…
第h-1層，$2^{h?2}$ 個結點，需要向下移動1層

則需要移動結點總的移動步數為：每層結點個數乘向下調整次數

$$T(h)=2^0?(h?1)+2^1?(h?2)+2^2?(h?3)+2^3?(h?4)+\dots \dots +2^{h?3}?2+2^{h?2}?1$$

利用數列的錯位相減（計算步驟如下圖）

得出：
$$T(h)=2^h?1?h$$
根據?叉樹的性質：
$$n=2^h?1和h=lo{g}_2(n+1)$$

得出：
$$T(n)=n?lo{g}_2(n+1)\approx n$$

向下調整算法建堆時間復雜度為：O(n)

---

3.2 向上調整時間復雜度($n?logn$)

與向下調整類似，計算所有結點向上移動至堆頂的移動總次數即可
設樹的高度為h
我們需要計算的是向上移動的總次數T(n)

分析：
第1層，$2^0$個結點，需要向下移動0層
第2層，$2^1$個結點，需要向下移動1層
第3層，$2^2$個結點，需要向下移動2層
第4層，$2^3$個結點，需要向下移動3層
…
第h層，$2^{h?2}$ 個結點，需要向下移動h-1層

則需要移動結點總的移動步數為：每層結點個數乘向上調整次數（第?層調整次數為0）

$$T(h)=2^1?1+2^2?2+2^3?3+\dots \dots +2^{h?2}?（h?2）+2^{h?1}?(h?1)$$

也是利用數列的錯位相減得：
$$T(h)=?(2^h?1)+2^h?（h?1）+2^0$$
根據?叉樹的性質：
$$n=2^h?1和h=lo{g}_2(n+1)$$

得出：
$$T(n)=(n+1)(lo{g}_2(n+1)?2)+2\approx n?lo{g}_{2}n$$

向上調整算法建堆時間復雜度為：$n?logn$

---

3.3 結論

由此可見，向下調整的效率是優于向上調整的，所以我們以后需要建堆時，應該優先考慮向下調整建堆。再后面的堆排序中我們可以深刻體會到。

---