【数据结构】堆的实现

1. 堆向上调整算法

1.1 时间复杂度编辑

2. 堆向下调整算法

2.1 时间复杂度

3. 建堆算法

3.1 向上调整建堆

3.2 向下调整建堆

4. 建堆算法的时间复杂度

5. 关于堆排序建大小堆问题

6. 堆排序

6.1 堆排序的时间复杂度

7.Top_k问题

8. 实现堆

8.1 初始化堆

8.2 销毁堆

8.3 堆的插入

8.4 堆的删除

8.5 获取堆顶数据

8.6 获取堆的数据个数

8.7 堆的判空

9. 总结

Heap.c

Heap.h

1. 堆向上调整算法

基本思想：

向堆尾插入新元素时，维护堆的性质，需要对该元素向上调整，从新插入的节点开始，与其父节点比较，若新节点的值比其父节点的值小，则交换它们，并将新节点的父节点当作目标节点继续向上调整，若目标结点的值比其父结点的值大，就停止向上调整，此时该树已成堆。（以小堆调整为例）

代码实现：

//交换函数
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;}}
}

1.1 时间复杂度

向上调整算法，插入一个节点，最多走log₂N次，时间复杂度为O(logN)。

2. 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。

向下调整算法有一个前提：

若想将此二叉树调整为小堆，左右子树都必须是一个小堆，才能调整。

若想将此二叉树调整为大堆，左右子树都必须是一个大堆，才能调整。

代码实现：

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整（小堆）
void AdjustDown(HPDataType* a, int n,int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;//先默认其左孩子的值较小while (child < n)   //child>=n说明孩子不存在，已经调整到叶子节点了{//找出小的那个孩子if (child+1<n && a[child + 1] < a[child])//如果右孩子的值小于左孩子  兼容一下最后面只有左孩子的情况防止child+1越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}

2.1 时间复杂度

向下调整算法，从根节点开始向下调整，最多走高度(log₂N)次，时间复杂度为O(logN)。

3. 建堆算法

3.1 向上调整建堆

代码实现：

void HeapSort(int* p, int n)
{//向上调整建堆 时间复杂度O(N*logN)for (int i = 1; i < n; i++){		AdjustUp(p, i);  //降序（建小堆）;升序（建大堆） //直接传数组的地址，把它当成一个堆		}
}
int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));return 0;
}

由于使用堆的向下调整算法有一个前提，要求左右子树均为大堆或小堆，那么对于任意树，如何把它调整成堆呢？

从倒数第一个非叶子结点开始，从后向前调整，一直调整到根结点就成堆了。

3.2 向下调整建堆

代码实现：

void HeapSort(int* p, int n)
{//向下调整建堆    时间复杂度为O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--) //从倒数第一个非叶子节点开始向下调整{     AdjustDown(p, n, i);}	
}int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));return 0;
}

4. 建堆算法的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简便使用满二叉树来证明(看近似值，多几个结点不影响最终结果)：

我们很容易认为向下调整建堆的时间复杂度是O(N)=(n - 1 - 1) / 2*logN=N*logN，接下来推理一下：
    //向下调整建堆  for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(p, n, i);}

总结：向下调整建堆的时间复杂度为O(N）

总结：向上调整建堆的时间复杂度为O(N*logN）

所以我们发现向下调整建堆比向上调整建堆时间复杂度更优，当进行堆排序时，建堆的时候需要向下调整，排序的时候需要向下调整，这样只需要封装一个向下调整函数就可以了。

5. 关于堆排序建大小堆问题

思考一下：当要让一组数据降序排列时，我们建大堆还是小堆呢?

通常我们会建大堆，其实如果建大堆，第一个数据是最大的，它已经被排好了，再要从剩下的数据中选出次大的，再把剩下的数据看作一个堆，此时数据间的关系全部混乱，需要重新建堆，但是代价太大了。正确的做法是建小堆，让首尾数据交换，尾数据即最小的数，再进行向下调整，调整到第一个数据是次小的。

堆排序若排升序，则要建大堆
堆排序若排降序，则要建小堆

6. 堆排序

基本思想：

把无序数组使用向下调整建堆算法构建成堆，首尾元素交换，堆顶最小的元素被替换到最后面，再向下调整，第二小的元素会成为堆顶元素，每次调整的范围都减少一个即排除掉最后一个元素，反复交换，反复调节，直到堆的大小变成1。

代码实现：

#include<stdio.h>//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整（建小堆）
void AdjustDown(int* a, int n,int parent)
{//先假设左孩子小(假设法)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 HeapSort(int* p, int n)
{//向下调整建堆  时间复杂度为O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从倒数第一个非叶子节点开始向下调整{AdjustDown(p, n, i);}//时间复杂度为O(N*logN)   int end = n - 1;  //n-1为堆最后一个数据的下标while (end > 0){Swap(&p[0], &p[end]);//首尾交换AdjustDown(p, end, 0);//向下调整  需调整的数据个数为end个--end;}
}int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));for (int i = 0; i < sizeof(p) / sizeof(p[0]); i++){printf("%d ", p[i]);}printf("\n");return 0;
}

运行结果：

6.1 堆排序的时间复杂度

我们已知向下调整建堆的时间复杂度为O(N)，在排序的过程中，每次要选出剩余数中的最大的树，再进行向下调整，总共需要执行N次，而向下调整算法的时间复杂度为O(logN)，进行N次即O(N*logN),整个过程的时间复杂度为O(N+N*logN)即为O(N*logN)。

7.Top_k问题

问题描述：

从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。

在生活中有很多涉及top-k问题，比如世界五百强，学校专业前几名，富豪榜等等。对于TOP-K问题，可能第一反应是用排序，将前几名排序出来，但当数据量很大很大时，排序就不好处理了，数据不能一下完全加载到内存中去。而解决这样的问题，最好的方式是用堆来处理。

基本思想：

先用前k个元素生成一个小堆，这个小堆用于存储当前最大的k个元素，接着，从k+1个元素开始扫描，如果扫描到的元素比堆顶数据大，就替换掉它，并进行向下调整，保证堆内的数据总是当前最大的k个数。得到的Top-k是未排序的。

时间复杂度：O(k)+O((N-k)*logk)=O(N*logk)，这里就不合并了。

其实通过复杂度可以看出，这样做效率并没有太大的提升，但是空间消耗极少。

找前k个最大的元素，就建小堆。
找前k个最小的元素，就建大堆。

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPDataType;
//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//先假设左孩子小(假设法)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 CreateNDate()
{	int n = 100000;srand(time(0));const char* file = "data,txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 100000;//造出来的数比100000小fprintf(fin, "%d\n", x);}fclose(fin);
}void TestHeap()
{int k;printf("请输入k:  ");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}const char* file = "data,txt";FILE* pf = fopen(file, "r");if (pf == NULL){perror("fopen error");return;}//读取文件中前k个数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, k, i);}//读取剩下的N-K个数int x = 0;while (fscanf(pf,"%d", &x)>0 ){if (x > kminheap[0]) //如果读取到的值比堆顶数据大{kminheap[0] = x; //替换堆顶数据AdjustDown(kminheap, k, 0);}}printf("最大前%d个数：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");}int main()
{		//CreateNDate();TestHeap();return 0;
}

我们造了十万个数据，要找最大的前k个，我们怎么验证得到的数据是不是最大的前k个呢？

把找数据函数代码屏蔽掉造数据，再把造数据代码屏蔽掉，去往装数据的文件里随机改动数据，运行找数据函数，就会发现我们改动的数据被找了出来，因为其它数据都比100000小，我们改动的数据比100000大，比较显眼，以此来判断我们的代码是否有问题。

运行结果：

8. 实现堆

8.1 初始化堆

创建一个堆类型

typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{HPDataType* a; //用于存储数据的数组int size;      //记录堆中已有的元素个数int capacity;  //堆的容量
}HP;

//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

8.2 销毁堆

为了避免内存泄漏，动态开辟的内存空间使用完之后后要及时释放。

//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

8.3 堆的插入

插入数据到数组的末尾，即树形结构的最后一个结点，插入完数据之后我们需要进行向上调整，使其在插入数据后仍然保持堆的结构。

//堆的插入
void HPPush(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");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整
}

8.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根和最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。

删除堆堆顶数据，不能挪动覆盖删除，不然关系就全部混乱了，我们把堆顶数据和最后一个数据交换，再删除最后一个数据，然后进行向下调整，调整完后堆顶数据依然是最小的，相较于删除的那个数据是次小的。所以在日常应用中，当数据量很多的时候，想要找较大或较小的几个数据，直接pop几次就可以了。

//堆的删除
void HPPop(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);
}

8.5 获取堆顶数据

//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

8.6 获取堆的数据个数

//获取堆的数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}

8.7 堆的判空

//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

9. 总结

Heap.c

#include"Heap.h"//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}//销毁堆
void HPDestroy(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;}}
}//堆的插入
void HPPush(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");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整
}//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;//先默认其左孩子的值较小while (child < n)   //child>=n说明孩子不存在，已经调整到叶子节点了{//找出小的那个孩子if (child+1<n && a[child + 1] < a[child])//如果右孩子的值小于左孩子  兼容一下最后面只有左孩子的情况防止child+1越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}//堆的删除
void HPPop(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 HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//获取堆的数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HPDataType x);
//堆的删除
void HPPop(HP* php);
//获取堆顶数据
HPDataType HPTop(HP* php);
//获取堆的数据个数
int HPSize(HP* php);
//堆的判空
bool HPEmpty(HP* php);