目录
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);