阅读量:0
1.堆的概念与结构
如果有⼀个关键码的集合 ，把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储，在⼀个⼀维数组中，并满⾜： （ 且 ）， i = 0、1、2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。
2.堆的性质
• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
• 堆总是⼀棵完全⼆叉树。
3.堆的实现
3.1初始化及基础功能
typedef struct heap { int* a; int size; int capacity; }HP; void heapinit(HP* php) { assert(php); php->a = NULL; php->size = 0; php->capacity = 0; } //初始化 void swap(int* p1, int* p2) { int t = 0; t = *p1; *p1 = *p2; *p2 = t; } //交换函数 void heappush(HP* php, int data) { if (php->size == php->capacity) //如果内存空间满了 { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; //内存空间和元素数量一样》》》》》1.内存空间为0，令内存大小为4， 2.内存空间满了，扩容至两倍大 int* tmp = (int*)realloc(php->a, newcapacity * sizeof(int)); //开辟内存空间记得加sizeof(sldatatype) php->a = tmp; //开辟内存空间赋给a指针 php->capacity = newcapacity; //设置新的容量 } php->a[php->size] = data; php->size++; adjustup(php->a, php->size - 1); } void heappop(HP* php) { swap(&php->a[0],&php->a[php->size - 1]); php->size--; adjustdown(php->a,php->size-1,0);//首尾互换！！！！！！，可以保证根节点以下的二叉树均不被改变（即排好序），只需由新的根节点从上往下排序交换一轮 } bool heapempty(HP* php) { return php->size == 0; } //判断是否为空 int heaptop(HP* php) { assert(php); return php->a[0]; } //取根节点 3.2 向上调整算法
向上调整算法
• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
（要求插入前必须是堆）！！！！！！
void adjustup(int* a, int child) //向上调整法 //上方必须是堆 { int parent = (child-1)/2; while (child>0) { if (a[parent]<=a[child]) //小堆为>=,大堆为<= { swap(&a[parent],&a[child]); child = parent; parent = (child - 1)/2; } else { break; } } }3.3 向下调整算法
向下调整算法
• 将堆顶元素与堆中最后⼀个元素进⾏交换
• 删除堆中最后⼀个元素
• 将堆顶元素向下调整到满⾜堆特性为⽌
！！！！！！向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。
void adjustdown(int* a,int n, int parent) //向下调整法，！！！！！！（仅适用于根结点两端都是大堆或小堆） { int child = 2 * parent + 1; while (child<=n) // { if (child + 1<=n && a[child + 1] > a[child]) // child+1>n可以推出child==n，所以只有左孩子 { child++; //选出左右孩子中最大的一个‘>’,最小的为'<' } if (a[parent]<=a[child]) //大堆为“<=”,小堆为“>=” { swap(&a[parent], &a[child]); parent = child; child = 2 * parent + 1; //每次都先找左孩子 } else { break; } } }
4.堆排序
int main() { int a[] = { 65,100,70,32,50,35 }; int i; int n = sizeof(a) / sizeof(a[0]); int flag = n; for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) //i从1开始，因为只有一个元素时可以视作堆 { adjustup(a, i); } //升序排序前的第一步，建立大堆,i从1开始，因为i=0时可视作堆，从1开始向上调整 //记住，只是建好了堆，堆不代表直接打印出来是有序的！！！！！！！！！还需要调整 while (n>0) //上文所说的调整，因为是大堆，所以root一定是最大的 { swap(&a[0],&a[n-1]);//将最大的换到tail n--; //不再关注最大的tail adjustdown(a,n-1, 0);//排除tail后重新建立大堆，选择从根开始的向下调整最合适（交换后，根的左右两边都是堆，只是根变了），让第二大的变为root，循环 } for (i = 0; i <= flag - 1; i++) printf("%d ",a[i]); return 0; }5.实际问题解决 ——topK问题
TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：
1）⽤数据集合中前K个元素来建堆
前k个最⼤的元素，则建⼩堆
前k个最⼩的元素，则建⼤堆
2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素
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) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void topk() { printf("请输⼊k：>"); int k = 0; scanf("%d", &k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } int val = 0; int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc error"); return; } for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); } // 建k个数据的⼩堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(minheap, k, i); } int x = 0; while (fscanf(fout, "%d", &x) != EOF) { // 读取剩余数据，⽐堆顶的值⼤，就替换他进堆 if (x > minheap[0]) { minheap[0] = x; AdjustDown(minheap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", minheap[i]); } fclose(fout); }
