1. 二叉樹的順序結構

普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中通常 把堆使用順序結構的數組來存儲 ，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構（完全二叉樹），一個是操作系統中管理內存區域分段。

2. 堆的概念

堆是將數組數據看作一顆完全二叉樹。遞增遞減數組一定是堆，堆不一定是遞增遞減數組。在實際意義中，堆可以實現堆排序，時間復雜度是 O(N*longN) ，提高查找效率，解決top k問題。

堆的性質：

1）堆總是一棵完全二叉樹

2）堆中某個節點的值總是不大于或不小于其父節點的值

3. 堆的分類

堆可以分為大堆和小堆：

大堆要求： 任意一個父親 <= 孩子

小堆要求： 任意一個父親 >= 孩子

4. 堆的實現（數組小堆）

這里將著重利用父子節點之間的關系完成堆的構建以及各類接口的實現：

leftchild = parent*2+1	# 奇數
rightchild = parent*2+2	# 偶數
parent = (child-1)/2	# 不區分左右孩子

如果要實現大堆，就將對應的向下調整算法和向上調整算法的判定更改即可實現。下面將其分為3個模塊進行實現小堆Heap.h，Heap.c，test.c

4.1 接口設計（Heap.h）

堆的結構設計和順序表類似，這里將采用小堆進行設計接口，對堆插入數據時，就要按照堆的規則進行構建。需要注意的是，堆的刪除是刪除跟節點數據。

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestory(HP* php);
// 小堆
// 插入，時間復雜度是O(logN)
void HeapPush(HP* php, HPDataType x);
// 規定刪除堆頂，即根節點
// 挪動數據覆蓋刪除跟會出問題
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);

4.2 接口實現（Heap.c）

1）初始化銷毀

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

2）插入，時間復雜度是O(logN)

因為擴容操作只有 HeapPush 使用，因此不將其作為單獨函數。

插入的過程中要保證堆符合大堆或者小堆的規則，因此，要對其進行調整，這里將引入向上調整算法，并將其作為單獨函數。

向上調整算法主要利用父子下標的特性， 在數據插入成為葉子時，將其與父節點比較，直到滿足堆的規則 （這里小堆要滿足父節點小于等于子節點 ）

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;}}
}// 插入，時間復雜度是O(logN)
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

因為后續要重復進行交換，所以將其作為單獨一個函數

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

3）刪除，規定刪除堆頂，即根節點

刪除是刪頭，可以選出最大最小的數據，尾刪沒有多大意義。

有人會想到挪動數據覆蓋刪除根節點，但會出問題，而且數組不一定有序，挪動后整棵樹的父子關系就會全亂了，并且也可能就不是堆了。

因此，這里采用的辦法是首先進行首尾交換，然后尾刪，這樣左右子樹依舊是小堆，然后再用向下調整算法，從而將堆構建完成。

void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){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(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);// 不需要進行覆蓋php->size--;AdjustDown(php->a, php->size, 0);
}

4）堆頂數據、堆大小、堆空

這三個操作就相對簡單，返回堆頂元素要檢查堆是否為空。

HPDataType HeapTop(HP* php)
{assert(php);// 空assert(php->size > 0);return php->a[0];
}size_t HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

4.3 完整代碼

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestory(HP* php);
// 小堆
// 插入，時間復雜度是O(logN)
void HeapPush(HP* php, HPDataType x);
// 規定刪除堆頂，即根節點
// 挪動數據覆蓋刪除跟會出問題
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);

Heap.c

#include "Heap.h"// 初始化銷毀
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}// 實現小堆
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}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;}}
}// 插入，時間復雜度是O(logN)
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}// 規定刪除堆頂，即根節點
// 挪動數據覆蓋刪除跟會出問題
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){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(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);// 空assert(php->size > 0);return php->a[0];
}size_t HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

test.c

#include "Heap.h"int main()
{int a[] = { 2,7,0,21,56,786,1,3 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}int k = 7;printf("打印小堆頂前7個數據：\n");while (k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}printf("\n堆大小為：%d, 堆是否為空：%d\n", HeapSize(&hp), HeapEmpty(&hp));printf("銷毀小堆！\n");HeapDestory(&hp);return 0;
}

運行效果

在學會堆的知識后，我們應該怎么應用呢?
下面將介紹兩個使用的堆使用：
堆排序&TopK問題：堆的實際應用：堆排序&TopK問題