數據結構（C）：從初識堆到堆排序的實現

🌞0.前言

🚈?1.堆的概念

🚈?2.堆的實現

🚝2.1堆向下調整算法

🚝2.2堆的創建（堆向下調整算法）

??2.2.1 向下調整建堆時間復雜度

🚝2.3堆向上調整算法

🚝2.4堆的創建（堆向上調整算法）

??2.4.1向上調整算法建堆的時間復雜度

🚝2.5堆的插入

🚝2.6堆的刪除

🚝2.7建堆的代碼實現

??2.7.1向下調整實現堆的建立

??2.7.2向上調整實現堆的建立

🚈?3.完整的堆的代碼的實現

🚝3.1堆的創建

🚝3.2堆的銷毀

🚝3.3堆的插入

🚝3.4堆的刪除（頭刪）

🚝3.5取堆頂元素的數據

🚝3.6 堆的數據個數

🚝3.7堆的判空

🚈?4.堆的應用堆排序

?5.結束語

🌞0.前言

? ? ? ? 言C之言，聊C之識，以C會友，共向遠方。各位博友的各位你們好啊，這里是持續分享數據結構知識的小趙同學，今天要分享的數據結構知識是堆，在這一章，小趙將會向大家展開聊聊堆的相關知識。?

🚈?1.堆的概念

堆就是以二叉樹的順序存儲方式來存儲元素，同時又要滿足 父親結點存儲數據都要大于等于兒子結點存儲數據（也可以是父親結點數據都要小于等于兒子結點數據）的一種數據結構。堆只有兩種即大堆和小堆，大堆就是父親結點數據大于等于兒子結點數據，小堆則反之。

同時這里要注意的是堆一定是完全二叉樹，不然就不是堆。那完全二叉樹是什么呢？這個地方不懂的博友可以看我們的這一篇博客：數據結構（C）樹的概念和二叉樹初見http://t.csdnimg.cn/JnWfb

如果看完了還是不明白可以私信小趙詢問哦。

好了下面讓我們看看上面說的兩種堆在圖上是怎么呈現的呢？

我們發現我們的任意一個父節點都比他的兩個子節點大（或等于）這個時候這就是一個大堆。?

我們發現我們的任意一個父節點都比他的兩個子節點小（或等于）這個時候這就是一個小堆。?

雖然堆是完全二叉樹，但其的存儲方式卻與二叉樹不同，我們一般存儲堆的方式是數組。而我們上面所畫的叫邏輯結構，那怎么由數組的存儲方式，轉化為我們的邏輯結構呢？

我們在介紹二叉樹的時候其實也曾簡單的說過二叉樹是有順序的，是從上到下，從左向右的，按這個順序我們就可以給我們的二叉樹標序號。?

那么就可以我們的邏輯結構轉化成我們的數組結構了，既然我們已經會將邏輯結構轉化為數組結構了，那么將數組結構轉化為邏輯結構也就沒有這么難了，大家可以自己試試，如果實在實現不了也可以找小趙咨詢哦。?

🚈?2.堆的實現

🚝2.1堆向下調整算法

什么是向下調整算法呢？其實正如其名就是從上到下調整堆的意思。要想更深入了解這個東西就先來看這張圖。

看這張圖這是一個很明顯的小堆對吧，那我這個時候要你改成一個大堆怎么辦，這個時候的操作其實是2，3進行比較，然后拿出大的和1換這個就成大堆了。?

可如果這個時候我給你的是個這樣的堆你又該怎么辦（要改成小堆）

?其實這個時候也是可以操作的，因為下面是有序的堆，我們只需要按照前面的順序一步步來就可以完成了。只不過這個時候改成了選擇兩個子中的小的哪一個，因為我們要做得是小堆（這個時候之所以說他下面是有序的堆是因為蓋住最上面的一個，下面的兩個堆都是小堆，我們要改成的也是小堆。）

那如果是無序的呢？?（改成小堆)

這個時候我們發現我們再想把這個改成小堆的難度就很大了。

🚝2.2堆的創建（堆向下調整算法）

那通過上面的實驗我們發現，想通過一個位置來做上面的操作，并把整個堆都變成小（大）堆，必須下面就是一個小（大）堆。所以我們的向下調整其實也是從最下面的開始的，而且我們剛剛做的步驟其實就是向下調整。?

那么再面對上面那個無序的堆我們也就有方法了。

這個時候我們就可以做到將無序的堆轉化成有序的堆了。?那么這個時候我們面對任何一個無序的數組，都可以通過這樣的方式將他轉化成堆.（至少在邏輯圖上可以實現，代碼實現下面說）

??2.2.1 向下調整建堆時間復雜度

每層節點個數 × 最壞情況向下調整次數：
T(N) = 2^(h-2) × 1 + 2^(h-3) × 2 + … … + 2^1 × (h-2)+2^0*(h-1)

錯位相減法
等號左右兩邊乘個 2 得到一個新公式，再用新公式減去舊的公式，具體見下圖

🚝2.3堆向上調整算法

聊了向下調整算法，那么其實也有向上調整算法。

如這里我們如何把這個堆改成大堆

向上調整一般是怎么玩的呢，一般我們的向上調整法就是從下面往上調整，向這里要想調整到我們想要的樣子就要三步

🚝2.4堆的創建（堆向上調整算法）

這里呢也和上面一樣，向上調整的地方的上面必須是已經調整好的，所以我們一般用向上調整法去建堆的時候往往要從第一個開始建堆到最下面。

??2.4.1向上調整算法建堆的時間復雜度

T(N) = 2^1× 1 + 2^2× 2 + 2^3 ×3+ … … + 2^(h-3)× (h-3) + 2^(h-2) × (h-2)+ 2^(h-1) × (h-1)

綜上：向下調整建堆要更優秀，效率更高

但總的來建堆的時間復雜度是O(N*logN)

🚝2.5堆的插入

像我們一般堆是用數組存儲的，我們一般插入也是從數組后面插入，所以也就是在最后一個位置插入，而這個時候上面的堆都是有順序的，我們可以用我們的向上調整算法來解決堆的插入。

🚝2.6堆的刪除

堆的刪除，我們一般針對的是頭元素的刪除，這個時候我們采取的策略是將頭元素和尾元素交換，然后讓頭元素，向下調整（因為下面的堆都已經是有順序的）

這樣就可以完成頭刪了?

🚝2.7建堆的代碼實現

代碼的實現我們的表示表示方式和前面的雙親節點是對應的（parent），然后子節點就是（child）

??2.7.1向下調整實現堆的建立

//小堆的建立
void Swap(int* a, int* b)//交換
{int tmp = *a;*a = *b;*b = tmp;
}
//小堆
void ADjustDown(int *a,int parent,int n)
{int 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;}}
}
void Heap(int *a,int n)
{int i = (n - 1 - 1) / 2;//找到最后一個雙親節點while (i >= 0){ADjustDown(a, i, n);i--;}
}
int main()
{int a[10] = { 3,5,9,8,6,1,5,2,6,323 };Heap(a, 10);
}

這里的主要方式就是我們前面的圖所演示的，就是從最后一個雙親節點向下調整，然后調整過程中要小心不要讓字節出了數組的范圍，同時要記住子節點和雙親節點的關系。?這樣可以方便我們的代碼的實現。

??2.7.2向上調整實現堆的建立

//建立小堆
void Swap(int* a, int* b)//交換
{int tmp = *a;*a = *b;*b = tmp;
}
void ADjustUp(int*a,int child,int n)
{int parent = (child - 1) / 2;//雙親節點和子節點關系while (parent >= 0){if (a[child] < a[parent])//如果子節點比雙親節點小，那么交換，并且向上移動{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1 - 1) / 2;}else{break;}}
}
void Heap(int* a, int n)
{int i = 0;while (i < n)//從最上面開始建堆{ADjustUp(a, i, n);i++;}
}
int main()
{int a[10] = { 3,5,9,87,6,12,7,11,13,1 };Heap(a, 10);
}

這里也基本上就是我們上面邏輯的實現，向上建堆，就要保證上面都是已經建好的堆，那么就得從首元素開始依次向下，建堆。?

🚈?3.完整的堆的代碼的實現

要想實現完整的堆的實現就要實現以下幾個函數

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
// 堆的構建
void HeapCreate(Heap* hp, HPDataType* a, int n)；
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂的數據
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

這樣我們的堆就可以像之前的鏈表順序表等一樣使用了。?

🚝3.1堆的創建

和上面的代碼邏輯基本一樣。

這里我們主要采用的是向下排序建堆，因為向下排序的時間復雜度低。

void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->_a == NULL){perror("malloc failed");}memcpy(hp->_a, a, n);hp->_capacity = n;hp->_size = n;int i = (n - 1 - 1) / 2;while (i >= 0){ADjustDown(a, i, n);i--;}
}