堆的实现源码
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> #include <stdbool.h> #include <assert.h> typedef struct Heap { int* a; int size; int capacity; }Heap; void HeapInit(Heap* st) { st->a = NULL; st->capacity = 0; st->size = 0; } void swap(int* str1, int* str2) { int tmp = *str1; *str1 = *str2; *str2 = tmp; } void Adjustup(int* 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 HeapPush(Heap* st, int x) { if (st->capacity == st->size) { int newcapcity = st->capacity == 0 ? 4 : st->capacity * 2; int* tmp = (int*)realloc(st->a, newcapcity * sizeof(int)); if (tmp == NULL) { perror("realloc fail"); } st->a = tmp; st->capacity = newcapcity; } st->a[st->size] = x; st->size++; Adjustup(st->a, st->size - 1); } void Heapprint(Heap* st) { for (int i = 0; i < st->size; i++) { printf("%d ", st->a[i]); } } 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; } } } bool HeapEmpty(Heap* st) { assert(st); if (st->size == 0) { return true; } else { return false; } } int HeapSize(Heap* st) { assert(st); return st->size; } void HeapPop(Heap* hp) { assert(hp); assert(!HeapEmpty(hp)); swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; AdjustDown(hp->a, hp->size, 0); } void HeapDestroy(Heap* st) { assert(st); free(st->a); st->a = NULL; st->size = 0; st->capacity = 0; } int HeapTop(Heap* st) { assert(st); assert(!HeapEmpty(st)); return st->a[0]; }
使用堆结构实现堆排序
void HeapSort(int* a, int n) { Heap hp; HeapInit(&hp);//初始化堆 for (int i = 0; i < 10; i++) { HeapPush(&hp, a[i]);//堆中插入元素,每次插入做向上调整.保证堆是小堆 } while (!HeapEmpty(&hp))//如果堆不为空的话 { int top=HeapTop(&hp);//每次取堆顶数据为最小 printf("%d ", top); HeapPop(&hp);//删除堆顶元素时,重新调整堆,使其还是小堆 } }
主函数
int main() { int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); }
编译运行
如果用上述方法写堆的话,还必须写一个堆的结构,特别麻烦.
排序方法2
1.排列升序
我们可以直接使用向上调整和向下调整建堆,实质上的堆只是数组,向上调正和向下调整只是操作下标而已.
排列升序我们应该创建大堆还是小堆,如果不仔细想一想的话,可能是创建一个小堆,然后依次取对顶元素,但是如果依次取堆顶元素的话,剩下的元素就不能构成一个堆,堆的关系就全乱了.如下图所示.取出堆顶的小元素.重新排列的话.
因此我们如果要排升序的话,就创建大堆,我们既可以用向上调整创建大堆,也可以用向下调整创建大堆
向下调整创建大堆
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* a, int n) { Heap hp; for (int i = (n - 1 - 1) / 2; i >=0; --i)//从最后一个非子叶节点开始走.直到堆顶的元素 { AdjustDown(a, n, i); } } int main() { Heap hp; //createdata(); //printtopK(10); int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
向上调整创建大堆
void Adjustup(int* 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 HeapSort(int* a, int n) { Heap hp; for (int i = 1; i < n; i++) { Adjustup(a, i); } //for (int i = (n - 1 - 1) / 2; i >=0; --i) //{ // AdjustDown(a, n, i); //} } int main() { Heap hp; //createdata(); //printtopK(10); int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
创建的大堆
然后将创建好的大堆进行排序
修改后的堆排序
void HeapSort(int* a, int n) { Heap hp; for (int i = (n - 1 - 1) / 2; i >=0; --i) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
排降序
由排升序创建大堆,则排降序创建小堆,创建小堆既可以用向上调整法,还可以使用向下调整
向下调整创建小堆
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* a, int n) { Heap hp; for (int i = (n - 1 - 1) / 2; i >=0; --i) { AdjustDown(a, n, i); } } int main() { Heap hp; //createdata(); //printtopK(10); int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
向上调整创建小堆
void Adjustup(int* 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 HeapSort(int* a, int n) { Heap hp; for (int i = 1; i < n; i++) { Adjustup(a, i); } //for (int i = (n - 1 - 1) / 2; i >=0; --i) //{ // AdjustDown(a, n, i); //} } int main() { Heap hp; //createdata(); //printtopK(10); int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
将创建好的小堆进行排序
void Adjustup(int* 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 HeapSort(int* a, int n) { Heap hp; for (int i = 1; i < n; i++) { Adjustup(a, i); } //for (int i = (n - 1 - 1) / 2; i >=0; --i) //{ // AdjustDown(a, n, i); //} int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } int main() { Heap hp; //createdata(); //printtopK(10); int arr[10] = { 52,85,74,46,23,14,65,25,32,78 }; HeapSort(arr, 10); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
总结:创建大堆或者小堆都可以用向上调整和向下调整,如果创建大堆对应的调整必须修改成孩子大于父亲进行交换,这样的话就可以把大数放在堆顶上.,如果创建小堆的话,孩子小于父亲的话,在进行交换,值得注意的是,创建大堆时,并且使用向下调整的话,需要将孩子的下标落在左右孩子较大的孩子身上.创建小堆时,需要将孩子的下标落在左右孩子较小的身上.
top-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
- 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
找最大的10个
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include <stdlib.h>//srand头文件 #include <time.h>//time头文件 void swap(int* str1, int* str2)//交换两个数据的值 { int tmp = *str1; *str1 = *str2; *str2 = 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 createdata() { int n = 10000; srand((unsigned int)time(NULL));//产生随机数种子 FILE* fp = fopen("xa.txt", "w");//以写的方式打开文件 if (fp == NULL) { perror("fopen fail"); return; } for (int i = 0; i < 10000; i++)//产生10000个随机数, { int x = rand()%10000;//并且每一个随机数都是小于10000. fprintf(fp,"%d\n",x);//将其写入文件中,并且换行 } fclose(fp); } void printtopk(int k) { FILE* fp = fopen("xa.txt", "r"); if (fp == NULL) { perror("fopen fail"); return; } int* kminheap = (int*)malloc(sizeof(int) * k);//动态申请10个空间大小 if (kminheap == NULL) { perror("malloc fail"); } for (int i = 0; i < k; i++) { fscanf(fp,"%d",&kminheap[i]);//先读取文件前10个数据 } for (int i = (k - 1 - 1) / 2; i >= 0; i--)//向下调整为小堆,因为选最大的10个要排小堆 { AdjustDown(kminheap, k, i); } int val = 0; while (!feof(fp))//文件中剩下的数据需要与小堆中堆顶元素比较,如果大于堆顶元素,就把堆顶元素更新 { fscanf(fp,"%d", &val);//读取文件中的数据到val中 if (val > kminheap[0]) { kminheap[0] = val; AdjustDown(kminheap, k,0);//比堆顶最小的大,就入堆,然后将堆顶元素向下调整,调整后,还需要保证是小堆。 } } for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } } int main() { createdata(); printtopk(10); }
找最小的10个
需要创建大堆
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include <stdlib.h> #include <time.h> void swap(int* str1, int* str2) { int tmp = *str1; *str1 = *str2; *str2 = 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 createdata() { int n = 10000; srand((unsigned int)time(NULL)); FILE* fp = fopen("xa.txt", "w"); if (fp == NULL) { perror("fopen fail"); return; } for (int i = 0; i < 10000; i++) { int x = rand()%10000; fprintf(fp,"%d\n",x); } fclose(fp); } void printtopk(int k) { FILE* fp = fopen("xa.txt", "r"); if (fp == NULL) { perror("fopen fail"); return; } int* kminheap = (int*)malloc(sizeof(int) * k); if (kminheap == NULL) { perror("malloc fail"); } for (int i = 0; i < k; i++) { fscanf(fp,"%d",&kminheap[i]); } for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(kminheap, k, i); } int val = 0; while (!feof(fp)) { fscanf(fp,"%d", &val); if (val <kminheap[0]) { kminheap[0] = val; AdjustDown(kminheap, k,0); } } for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } } int main() { createdata(); printtopk(10); }