一、堆的概念及结构

二、小根堆的实现

2.1 堆的数据结构

2.2 堆的初始化HeapInit

2.3 堆的销毁HeapDestory

2.4 堆的插入HeapPush

2.4.1 插入代码HeapPush

2.4.2 向上调整代码AdjustUp

2.4.3 交换数据代码Swap

2.5 堆的删除HeapPop

2.5.1 删除代码HeapPop

2.5.2 向下调整算法AdjustDown

2.6 取堆顶的数据HeapTop

2.7 获取堆的数据个数HeapSize

2.8 堆的判空HeapEmpty

三、堆的应用

3.1 堆排序

3.2 TOP-K问题

3.2.1 创建大量数据

3.2.2 求K个最大的元素

3.2.3 验证

四、代码

4.1 堆的代码

4.1.1 Heap.h

4.1.2 Heap.c

4.2 堆排序的代码

4.3 TOP-K的代码

一、堆的概念及结构

堆（Heap）是一种特殊的数据结构，通常以完全二叉树的形式呈现。

堆的核心特性是：

对于大根堆，任意父节点的值都大于或等于其子节点的值
对于小根堆，任意父节点的值都小于或等于其子节点的值

堆通常使用数组来模拟完全二叉树的结构。数组索引按照从上到下、从左到右的方式对应树的节点排列。假设某个节点在数组中的位置为i，则其左子节点和右子节点的位置分别为 2*i+1和 2*i+2，而其父节点的位置为(i-1)/2。

如下所示：

二、小根堆的实现

2.1 堆的数据结构

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

2.2 堆的初始化HeapInit

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

2.3 堆的销毁HeapDestory

// 堆的销毁
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}

2.4 堆的插入HeapPush

假如，我们现在有一个数组a:15 18 19 25 28 34 65 49 27 37，他从逻辑上看，是一个小根堆结构，我们将它的逻辑结构画出来如下所示：

我们现在想要将10插入堆里面去，插入10之后，要不允许破坏原本小根堆的结构，所以我们就需要将10一步一步的调整，如下所示：

2.4.1 插入代码HeapPush

// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4.2 向上调整代码AdjustUp

//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}

2.4.3 交换数据代码Swap

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}

2.5 堆的删除HeapPop

堆的删除，我们首先要确定删除哪一个元素，看上面的数组a:10 15 19 25 18 34 65 49 27 37 28.我们画出他的二叉树表现形式，如下所示，他满足小根堆特性。

现在数组中有这么多的元素，我们要删除哪一个呢？最常见的是删除第一个元素和最后一个元素，如果我们删除最后一个元素28，删除的没有意义，他既不是最大的也不是最小的，所以堆的删除一般都是删除堆顶元素，也就是以一个元素，删除堆顶元素之后，后面的元素需要向前移动吗？答案是不能，如果向前移动，元素之间的逻辑关系会改变，不满足小堆特性，所有如果我们要删除第一个元素，通常做法是将最后一个元素与第一个元素互换，只有第一个元素不满足小根堆的特性，其他元素都满足，我们还需要写一个向下调整算法。

2.5.1 删除代码HeapPop

// 堆的删除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}

2.5.2 向下调整算法AdjustDown

void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}

2.6 取堆顶的数据HeapTop

// 取堆顶的数据
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}

2.7 获取堆的数据个数HeapSize

// 堆的数据个数
int HeapSize(Heap* php) {assert(php);return php->size;
}

2.8 堆的判空HeapEmpty

// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

三、堆的应用

3.1 堆排序

如果我们想要升序的话，就需要建立大根堆。

如果我们想要降序的话，就需要建立小根堆。

现在我们有一个数组a{ 27,15,19,18,28,34,65,49,25,37 };我们想要将a进行从小到大排序，所以我们就需要对这个数组进行建堆处理。

那现在我们如何建堆呢？

方法一：我们可以访问数组的每一个元素，然后初始化一个堆，将数组的每一个元素插入到堆里面，我们根据堆的自动调整算法，可以自动的变成大根堆,然后我们取出堆顶的元素，把它放在数组里面，然后堆的删除，重复n次。但是这样空间复杂度太高了需要重新新建一个堆。

方法二：我们可以从数组的第二个元素开始，进行向上调整算法，就这个数组变成一个堆，如下所示：

for (int i = 1; i < size; i++) {AdjustUp(a, i);
}

我们打开我们的调试，看到数组a成功的变成了一个大根堆。但是这样时间复杂度太高了。

方法三：可以从最后一个分支节点开始，依次进行向下调整算法，如下所示：

for (int i =(size-2)/2 ; i >= 0; i--)//
{AdjustDown(a, i, size);
}

我们常用的建堆算法是方法三。

建完堆之后，我们将堆顶元素与最后一个元素互换，然后重新调整堆，重复n次。代码如下所示：

int end = size - 1;
while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;
}

这样我们就成功的将数组a从小到大排序了。

3.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

3.2.1 创建大量数据

我们使用代码创建大量的数据，如下所示：

void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = rand()+i;fprintf(pf, "%d\n", number);}
}

3.2.2 求K个最大的元素

首先，输入k的值，malloc出k个int类型的空间，然后从文件中读取前k个数，将他们放在malloc出来的空间里面，将他们建成小堆，最后依次读取文件中后n-k个，依次与堆顶进行比较，如果大于堆顶就替换，然后调整堆。代码如下：

void TOP_K() {printf("请输入k：");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//从文件中拷贝k个数到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//读取剩下的n-k个数据int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d个数", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}