【數據結構 · 初階】- 堆的實現

一.初始化

二.插入

?三.刪除（堆頂、根）

四.整體代碼

Heap.h

Test.c

Heap.c

我們使用順序結構實現完全二叉樹，也就是堆的實現

以前學的數據結構只是單純的存儲數據。堆除了存儲數據，還有其他的價值——排序。是一個功能性的數據結構

小根堆堆頂的數據一定是最小的，大根堆堆頂的數據一定是最大的
選出最大/最小，再選次大/次小……不斷選最后就幫助排序。還可以解決取前幾，后幾的TOP-K?問題?

我們以建大堆為例。建小堆只需改變爸 < 娃即可

一.初始化

下面多次用到交換，將交換分裝成函數

Heap.h

typedef int HPDataTypt;typedef struct Heap
{HPDataTypt* a; // 數組指針，指向要開辟的存儲數據的數組int size; // 當前已存儲的有效數據個數int capacity; // 最大容量
}HP;void HeapInit(HP* php); // 初始化
void HeapDestroy(HP* php); // 銷毀

Heap.c?

void HeapInit(HP* php)
{assert(php);php->a = (HPDataTypt*)malloc(sizeof(HPDataTypt) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}void Swap(HPDataTypt* p1, HPDataTypt* p2)
{HPDataTypt tmp = *p1;*p1 = *p2;*p2 = tmp;
}

php 是指向主函數中，HP(結構體類型)的變量 hp 地址的指針。php 中存放的是 hp 的地址。若為空就說明結構體沒有開好，所以一定不能為空，斷言。

二.插入

堆的底層就是數組，可以插入數據。要把控制數組想象成控制樹。原來是大根堆，插入后，要求還得是堆。
插入前是堆，插入后會影響部分祖先（跟祖先調整）

以大根堆為例，看最簡單的情況：插入20，插入后不影響堆的性質。

? ??

再插入60，插入后要調整。?

為保證父親 > 娃，要交換? ?

娃還> 父親，繼續交換?父親 > 娃，結束

上面的過程叫 向上調整?，最多調整高度次，時間復雜度：O( log N )。插入一個數據，想讓他再調整成堆只要?log N 次

堆的插入不像鏈表、順序表，不能想往哪插就往哪插，要保持性質。

上面的尾插，如果堆原來是這樣，就不能尾插20?

所以插入單純的叫 Push 就好，因為不是由接口指定在哪個位置插入。

void AdjustUp(HPDataTypt* 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; // 娃 <= 爸，不往上走}}
}void HeapPush(HP* php, HPDataTypt x)
{assert(php);if (php->size == php->capacity){HPDataTypt* tmp = (HPDataTypt*)realloc(php->a, sizeof(HPDataTypt) * php->capacity * 2);if (tmp == NULL){perror("malloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1); // 從孩子（插入數據）位置向上調整
}

?三.刪除（堆頂、根）

堆刪除，刪尾輕松，但無意義。

為什么刪堆頂、根才有意義？老大被干掉了，老二才能冒頭。

堆實現的意義，無論是排序還是 top-k ，本質是在幫我選數，選出最大/最小數

刪除后，也要保證是堆。要把最大的刪掉，怎么搞？

不能挪動刪除（直接刪）！原因：1.效率低下? ?2.父子兄弟關系全亂了

正確方法：(間接刪)?堆頂和最后的元素換一下；--size，使換下去的最后一個（原堆頂）元素失效
1.效率高? ?2.最大程度的保持了父子關系

單看左右子樹依舊是大堆，換上去的原最后元素大概率是比較小的，就要向下調整

看下面的新場景：為保證換了之后父親 > 娃，現在的堆頂（原最后一個元素）要跟大的娃換。

娃中大的 > 爸，把爸換下去?繼續換? ? ?

最壞情況調到葉子結束。物理上是數組，怎么判斷到葉子——沒有娃，怎么判斷沒有娃呢？
把它當做爸，算左娃的下標，如果超出數組范圍就沒娃，所以參數要多給個數組的大小 size，用來判斷 child 是否越界

最壞走高度?log N 次

void AdjustDown(HPDataTypt* a, int n, int parent)
{int child = parent * 2 + 1; // 默認左孩子大，將左孩子定為 childwhile (child < n){// 選出左右孩子中大的那一個if (child + 1 < n && a[child] < a[child + 1]) // 防止無右娃的越界風險{child++; // 如果右孩子大，++后，child 就是右孩子}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]); // 交換堆頂、最后元素php->size--; // 刪除換下來的原堆頂元素AdjustDown(php->a, php->size, 0); // 向下調整，0是開始調整位置的下標// n 是有效數據個數，作為下標，用來判斷 child 是否越界
}

向上調整的前提：除了 child 這個位置，前面的數據構成堆
向下調整的前提：保證左右子樹都是堆

四.整體代碼

Heap.h

typedef int HPDataTypt;typedef struct Heap
{HPDataTypt* a; // 數組指針，指向要開辟的存儲數據的數組int size; // 當前已存儲的有效數據個數int capacity; // 最大容量
}HP;void HeapInit(HP* php); // 初始化
void HeapDestroy(HP* php); // 銷毀void HeapPush(HP* php, HPDataTypt x); // 插入
void HeapPop(HP* php);// 刪除堆頂HPDataTypt HeapTop(HP* php); // 堆頂的數據
bool HeapEmpty(HP* php); // 探空
int HeapSize(HP* php);void AdjustUp(HPDataTypt* a, int child); // 向上調整
void AdjustDown(HPDataTypt* a, int n, int parent); // 向下調整

Test.c

void test1() // 排序
{HP hp;HeapInit(&hp);HeapPush(&hp, 2);HeapPush(&hp, 45);HeapPush(&hp, 76);HeapPush(&hp, 23);HeapPush(&hp, 5654);HeapPush(&hp, 24);HeapPush(&hp, 5);HeapPush(&hp, 242);HeapPush(&hp, 25);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);// 選老二，必須干掉老大}HeapDestroy(&hp);
}void test2() // top-k
{HP hp;HeapInit(&hp);HeapPush(&hp, 2);HeapPush(&hp, 45);HeapPush(&hp, 76);HeapPush(&hp, 23);HeapPush(&hp, 5654);HeapPush(&hp, 24);HeapPush(&hp, 5);HeapPush(&hp, 242);HeapPush(&hp, 25);HeapPush(&hp, 5);HeapPush(&hp, 5);int k = 0;scanf("%d", &k);while (!HeapEmpty(&hp) && k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);// 選老二，必須干掉老大}HeapDestroy(&hp);
}

Heap.c

void HeapInit(HP* php)
{assert(php);php->a = (HPDataTypt*)malloc(sizeof(HPDataTypt) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}void Swap(HPDataTypt* p1, HPDataTypt* p2)
{HPDataTypt tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataTypt* 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; // 娃 <= 爸，不往上走}}
}void HeapPush(HP* php, HPDataTypt x)
{assert(php);if (php->size == php->capacity){HPDataTypt* tmp = (HPDataTypt*)realloc(php->a, sizeof(HPDataTypt) * php->capacity * 2);if (tmp == NULL){perror("malloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1); // 從孩子（插入數據）位置向上調整
}void AdjustDown(HPDataTypt* a, int n, int parent)
{int child = parent * 2 + 1; // 默認左孩子大，將左孩子定為 childwhile (child < n){// 選出左右孩子中大的那一個if (child + 1 < n && a[child] < a[child + 1]) // 防止無右娃的越界風險{child++; // 如果右孩子大，++后，child 就是右孩子}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]); // 交換堆頂、最后元素php->size--; // 刪除換下來的原堆頂元素AdjustDown(php->a, php->size, 0); // 向下調整，0是開始調整位置的下標// n 是有效數據個數，作為下標，用來判斷 child 是否越界
}HPDataTypt HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}