文章目錄
前言
一、堆的概念與結構
二、堆的實現
堆的定義
1.初始化堆
2.堆的銷毀
3.堆的插入
3.1向上調整算法
4.堆的判空
5.求有效個數
6.刪除堆頂數據
6.1向下調整算法
7.獲取棧頂數據
三、完整源碼
總結
前言
上篇了解樹和二叉樹相關的概念，這篇學習一種特殊的二叉樹--堆，通過認識堆來實現堆和堆的應用。
一、堆的概念與結構
如果有一個關鍵碼的集合 K = { k0 , k1 , k2 , ...， k n?1 } ，把它的所有元素按完全二叉樹的順序存儲方式存儲，在一個一維數組中，并滿足： K i <= K2? i+1 （ K i >= K2? i+1 且 K i <= K2? i+2 ）， i = 0、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 否則無右孩子
二、堆的實現
堆的定義
由此，我們可知堆的底層是數組來實現的，則堆的結構是順序結構，可寫出堆的結構定義
typedef int HPDatatype;
//堆的結構
typedef struct Heap
{HPDatatype* arr;int size; //有效數據個數int capacity; //容量
}HP;1.初始化堆
代碼解析：
先對未開辟空間的數組指針置為空，再對有效個數和容量大小都置為0.
//初始化
void HPIint(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}2.堆的銷毀
代碼解析：
先判斷堆是否為空，不為空先對數組進行釋放再置為NULL，再對有效個數和容量大小都置為0
注：對堆開辟空間使用完后就要對堆進行銷毀，避免造成空間浪費，因此要對堆進行銷毀
//銷毀
void HPDesTroy(HP* php)
{//判斷堆是否為空，不為空就直接free再置空assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}3.堆的插入
代碼解析：
堆的插入就是在尾部進行數據插入。先判斷堆是否已滿，堆已滿就進行 realloc 增容并更新capacity。增容后，把插入進來的數據進行重新調整，用 AdjustUp 函數對堆進行調整
//往堆中插入數據(以建小堆為例)
void HPPush(HP* php, HPDatatype x)
{assert(php);if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//插入數據php->arr[php->size] = x;//插入數據后用向上調整方法來調整成小堆或者大堆AdjustUp(php->arr, php->size);++php->size;
}3.1向上調整算法
接下來給大家介紹AdjustUp 函數?
代碼解析：
先將元素插入到堆的末尾,即最后一個孩子之后插入之后如果堆的性質遭到破壞，將新插入結點順著其雙雙親往上調整到合適位置即可由二叉樹的性質，我們可知已知孩子結點可求父結點：Parent =(child-1)/2。在這里我們建小堆，要求孩子結點大于父結點，如果不滿足就對進行交換，在讓child 走到parent ，parent 走到parent 的父結點；如果滿足不用交換直接跳出循環。
//向上調整算法：
void AdjustUp(HPDatatype* arr, int child)
{//已知子節點下標，來求父節點下標int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent])//建大堆就大于{Swap(&arr[child], &arr[parent]);//交換后，子節點會跑到舊位置的父節點，則再求新位置的父節點child = parent;parent = (child - 1) / 2;}else {break;//如果子節點大于父節點，則不需要變化直接跳出循環}}
}時間復雜度：
因為堆是完全?叉樹，?滿?叉樹也是完全?叉樹，此處為了簡化使?滿?叉樹來證明(時間復雜度本來看的就是近似值，多?個結點不影響最終結果)分析：第1層， 2 0 個結點，需要向上移動0層第2層， 2 1 個結點，需要向上移動1層第3層， 2 2 個結點，需要向上移動2層第4層， 2 3 個結點，需要向上移動3層......第h層， 2 h ?1 個結點，需要向上移動h-1層則需要移動結點總的移動步數為：每層結點個數 * 向上調整次數（第?層調整次數為0）
4.堆的判空
代碼解析：用bool函數來判斷堆是否為空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}5.求有效個數
代碼解析：直接返回有效個數即可
int HPSize(HP* php)
{assert(php);return php->size;
}6.刪除堆頂數據
代碼解析：
先判斷堆是否為空堆，是就返回0，不是返回有效數據；讓根結點和最后一個元素進行交換，把交換后的最后一個元素刪除后，再進行向下調整算法
//刪除堆頂數據(以建小堆為例)
void HPPop(HP* php)
{assert(!HPEmpty(php));//交換根節點和最后一個節點，再對新的最后一個節點進行刪除Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//使用向下調整算法AdjustDown(php->arr, 0, php->size);}6.1向下調整算法
代碼解析：
將堆頂元素與堆中最后一個元素進行交換刪除堆中最后一個元素將堆頂元素向下調整到滿足堆特性為止由二叉樹的性質，我們可知，已知parent 結點的下標，就可求左，右孩子結點的下標，左下標：2(parent )+1=child, 右下標：2parent +2=child 。把最后一個元素刪除后，這里需要建小堆，先找到孩子結點中較小的結點，把父結點和較小的孩子結點進行交換，再讓父結點走到較小的孩子結點的交換前的位置，再更新孩子結點的下標；如果父結點小于孩子結點就不用交換，直接跳出循環。
//向下調整算法
void AdjustDown(HPDatatype* arr, int parent, int n)
{//已知父節點，求子節點又可求左右子節點int child = parent * 2 + 1;//左子節點while (child<n){//找到最小的節點，讓其與父節點進行交換，誰小誰往上調(如果是大堆，誰大誰往上調)if (child + 1 <n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//父節點走到舊的字節點下標，再求新子節點下標parent = child;child = parent * 2 + 1;}else {break;}}
}
時間復雜度：
第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層
則需要移動結點總的移動步數為：每層結點個數 * 向下調整次數
注：堆的向上調整算法和向下調整算法都可以建大堆和小堆。向上調整算法主要用于堆插入，向下調整算法主要用于堆應用和堆排序。通過兩者得出的時間復雜度，可知向下調整算法時間復雜度比向上調整算法復雜度好。
7.獲取棧頂數據
代碼解析：直接返回棧頂的數據
HPDatatype HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}三、完整源碼
Heap,h：
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//一、用順序結構實現完全二叉樹，底層是數組
typedef int HPDatatype;
//堆的結構
typedef struct Heap
{HPDatatype* arr;int size; //有效數據個數int capacity; //容量
}HP;//初始化
void HPIint(HP* php);
//銷毀
void HPDesTroy(HP* php);
//往堆中插入數據
void HPPush(HP* php, HPDatatype x);
//刪除堆頂數據
void HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
//獲取棧頂數據
HPDatatype HPTop(HP* php);//向上調整算法：
void AdjustUp(HPDatatype* arr, int child);
//向下調整算法
void AdjustDown(HPDatatype* arr, int parent, int n);
Heap,c：
#include"Heap.h"//初始化
void HPIint(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//銷毀
void HPDesTroy(HP* php)
{assert(php);//判斷堆是否為空，不為空就直接free再置空if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}//交換：父節點與子節點比較，誰小誰往上調(誰大誰往上調)
void Swap(int* x, int* y)
{int temp = *x;*x = *y;*y = temp;
}//向上調整算法：
void AdjustUp(HPDatatype* arr, int child)
{//已知子節點下標，來求父節點下標int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent])//建大堆就大于{Swap(&arr[child], &arr[parent]);//交換后，子節點會跑到舊位置的父節點，則再求新位置的父節點child = parent;parent = (child - 1) / 2;}else {break;//如果子節點大于父節點，則不需要變化直接跳出循環}}
}//往堆中插入數據(以建小堆為例)
void HPPush(HP* php, HPDatatype x)
{assert(php);if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//插入數據php->arr[php->size] = x;//插入數據后用向上調整方法來調整成小堆或者大堆AdjustUp(php->arr, php->size);++php->size;
}///
//對堆進行判斷是否為空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//求size
int HPSize(HP* php)
{assert(php);return php->size;
}//向下調整算法
void AdjustDown(HPDatatype* arr, int parent, int n)
{//已知父節點，求子節點又可求左右子節點int child = parent * 2 + 1;//左子節點while (child<n){//找到最小的節點，讓其與父節點進行交換，誰小誰往上調(如果是大堆，誰大誰往上調)if (child + 1 <n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//父節點走到舊的字節點下標，再求新子節點下標parent = child;child = parent * 2 + 1;}else {break;}}
}//刪除堆頂數據(以建小堆為例)
void HPPop(HP* php)
{assert(!HPEmpty(php));//交換根節點和最后一個節點，再對新的最后一個節點進行刪除Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//使用向下調整算法AdjustDown(php->arr, 0, php->size);}//獲取棧頂數據
HPDatatype HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}
test,c：
#include"Heap.h"void test()
{HP hp;HPIint(&hp);HPPush(&hp, 6);HPPush(&hp, 4);HPPush(&hp, 8);HPPush(&hp, 10);//HPPop(&hp);//HPPop(&hp);//HPPop(&hp);//HPPop(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);//取棧頂就要刪除棧頂，不然會一直循環}HPDesTroy(&hp);
}總結
非常感謝大家閱讀完這篇博客。希望這篇文章能夠為您帶來一些有價值的信息和啟示。如果您發現有問題或者有建議，歡迎在評論區留言，我們一起交流學習。
 平臺)
