2-4完整代码
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef struct Heap { int* a; int size; int capacity; }HP; void HeapInit(HP* php) { assert(php); php->a = (int*)malloc(sizeof(HP) * 4); php->size = 0; php->capacity = 4; } void HeapDestory(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; } void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void AdjustUp(int* 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; } else { break; } } } //插入X后继续保持堆形态 void HeapPush(HP* php, int x) { assert(php); if (php->size == php->capacity) { int newcapacity = 2 * php->capacity; int* temp = (int*)realloc(php->a, sizeof(int) * newcapacity); if (temp == NULL) { perror("realloc fail.\n"); exit(-1); } php->a = temp; php->capacity = newcapacity; } php->a[php->size] = x; php->size++; //向上调整算法，传要调整的数组和从哪个下标child开始调 AdjustUp(php->a, php->size - 1); } void HeapAdjustDown(int* a, int n, int parent) { int minchild = 2 * parent + 1; while (minchild < n) { if (minchild + 1 < n && a[minchild] > a[minchild + 1]) { minchild++; } if (a[minchild] < a[parent]) { Swap(&a[minchild], &a[parent]); parent = minchild; minchild = 2 * parent + 1; } else { break; } } } //删除堆顶元素，找到次小或次大的元素 //删除之后仍要尽量保持堆的形态 void HeapPop(HP* php) { assert(php); Swap(&php->a[0], &php->a[php->size - 1]); php->size--; HeapAdjustDown(php->a, php->size-1,0); } bool HeapEmpty(HP* php); int HeapTop(HP* php) { assert(php); assert(!HeapEmpty(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 HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } } int main() { int a[] = { 10,2,20,4,12,67,56,1 }; int size = sizeof(a) / sizeof(a[0]); HP heap; HeapInit(&heap); for (int i = 0; i < size; i++) { HeapPush(&heap, a[i]); } HeapPop(&heap); HeapPrint(&heap); HeapDestory(&heap); return 0; }
3.两种方法建堆:
从上面我们可以知道：我们已经学会了建堆以及堆的插入删除数据。
但是我们知道我们建好的堆并不是有序的，而且堆中的数组和待的数组还不是同一个数组，这就意味着如果要使待排序的数组有序的话，还得将堆中的数据通过heapTop函数和HeapPop函数不断先取出堆顶元素插入到待排序数组，后删除堆顶元素（向下调整法）....
最重要的话这样的话还会导致我们使用额外的空间来拷贝待排序的数组来建堆
因此问题来了：怎么将数组本身建立成一个堆，从而减少额外空间的开辟
如果随便给你一个数组,元素向后顺序随机,要你把这个数组建成一个小根堆.(比如 14, 12, 4, 3, 6, 68, 21, 2 )
3-1向上调整法建堆
向上调整法的使用前提:每插入一个元素前,原数组的逻辑二叉树必须是一个小根堆(大根堆).
那么我们可以把14默认为是一个符合前提的堆,然后从12往后不断向数组中插入元素,并不断向上调整,直至把整个数组元素全部插完,即完成堆的建立.
//向上调整法建堆 for (int i = 0; i < n; i++) { AdjustUp(a, i); }
3-2向下调整法建堆
向下调整法使用的前提:左子树和右子树必须是小根堆(大根堆)
由于排序的数组是随机给的,所以对于堆顶元素来说,其左子树和右子树大大部分都不是小根堆(大根堆),所以不能从第一个数组元素(堆顶)开始向下调整;同时,叶子节点不需要向下调整,所以我们采用从倒数第一个非叶子节点开始向下调整(当然如果代码中写的是从叶子节点开始向下调整,结果也没有问题,但是就是多次一举而已);
向下调整法建堆 //for (int i = (n - 1 - 1) / 2; i >= 0; i--) //{ // HeapAdjustDown(a, n, i); //}
3-3.完整代码
void HeapSort(int* a, int n) { //向上调整法建堆 for (int i = 0; i < n; i++) { AdjustUp(a, i); } 向下调整法建堆 //for (int i = (n - 1 - 1) / 2; i >= 0; i--) //{ // HeapAdjustDown(a, n, i); //} } void HeapPrint2(int* a, int n) { assert(a); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } } int main() { int a[]={ 14, 12, 4, 3, 6, 68, 21, 2 }; int sz = sizeof(a) / sizeof(a[0]); HeapSort(a, sz); HeapPrint2(a, sz); return 0; }
3-4.两种建堆方式的时间复杂度
时间复杂度=总调整次数=每一层节点个数*该层需要调整的次数
向下调整法建堆:LogN
向上调整法建立堆:NLogN
分析向上调整法和向下调整法建堆时间复杂度相差这么大的原因:
因为向下调整法的节点数量多的时候,需要调整的次数就少;
而向上调整法的节点数量多的时候,需要调整的次数也越多;
4.堆排序
前面我们学会了如何去高效的建立堆,其中我们优先采用时间复杂度更小的向下调整法建堆
我们直接在数组上建立了堆,那我们就可以接着通过选数,把数组进行排序,从而完成堆排序
那么问题又来了:如果我要排升序,我们应该建大堆还是小堆呐?
让我们想一想,如果要排升序,如果我们建立的是小堆的话,我们的确可以轻松的选出最小的数,但是如果我们在选次小的数的时候,就不得不破坏整个堆的结构,父子关系全乱了(和堆的插入和删除那里一样),这样下来重新建堆的话就是O(N)的时间复杂度;要选N个数,选一次数就要重新建一次堆的话,时间复杂度总体上就是O(N*N),那还不如直接遍历数组n次,也是N方,这样简直是拿着一手好牌,却打的稀烂!
所以我们升序的话采用建大堆的方式,那又有一个问题,建大堆后又是如何选出次小的呐?请往下看~~
代码如下:(在原来的基础上增加的选数的代码完成堆排序)
void HeapSort(int* a, int n) { //向下调整法建堆,时间复杂度:O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { HeapAdjustDown(a, n, i); } //升序-建小堆 //降序-建大堆 //选数:堆排序 int i = 1; //时间复杂度:O(NLogN) while (i < n) { Swap(&a[0], &a[n - i]); HeapAdjustDown(a, n - i, 0); ++i; } }
5.TopK问题
在一堆数中,我们如果要找前K个最大的数,该怎么做?
或许你脑海里最先想到的是用快排先排序,然后直接选择前K个数据，那代价有点大.
这里鉴于选择排序中的堆排序的选数的经验,我们考虑采用堆的选数的思想解决这个问题.
（这里因为数据量过大，担心内存空间不够大，我们选择在磁盘上存储这些数据）
这时我们优先选择建小堆，我们建一个K个数的小堆，然后将后N-K个数和堆顶元素比较，如果堆顶元素小于后N-K个树数，就交换，然后向下调整，以此类推。
#include<time.h> void CreateFileName(const char* filename, int N) { FILE* pf = fopen(filename, "w"); if (pf == NULL) { perror("fopen\n"); exit(-1); } //生成随机数 srand(time(0)); for (int i = 0; i < N; i++) { fprintf(pf, "%d ", rand() % 10000 + 1); } fclose(pf); pf = NULL; } void PrintTopK(const char* filename, int k) { FILE* pf = fopen(filename, "r"); if (pf == NULL) { perror("fopen\n"); exit(-1); } //文件读取前K个数 int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc"); exit(-1); } for (int i = 0; i < k; i++) { fscanf(pf,"%d", &minHeap[i]); } //建小堆 for (int i = (k-1-1)/2; i>=0;--i) { HeapAdjustDown(minHeap, k, i); } //后N-k个数和堆顶元素比较 int val = 0; while (fscanf(pf, "%d", &val)!=EOF) { if (val > minHeap[0]) { minHeap[0] = val; HeapAdjustDown(minHeap, k, 0); } } //打印出前k大的数 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(pf); pf = NULL; } int main() { const char* filename = "test.txt"; int N = 100; int k = 10; //给文件内随机生成N个数 CreateFileName(filename, N); //从文件中选出N个数中前K大的几个数字，并且打印 PrintTopK(filename, k); return 0; }
TopK问题的时间复杂度分析：
