各位CSDN的uu们你们好呀，好久不见，停更了很长一段时间吧，最近小雅兰会开始慢慢更新起来的，下面，就进入小雅兰今天的分享的知识点吧，让我们一起进入堆的世界！！！
堆排序——（1）
heap.h的内容：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HeapDataType; typedef struct Heap { HeapDataType* a; int size; int capacity; }Heap; //堆的初始化 void HeapInit(Heap* php); //堆的销毁 void HeapDestroy(Heap* php); //插入数据 void HeapPush(Heap* php, HeapDataType x); //向上调整算法 void AdjustUp(HeapDataType* a, int child); //删除堆顶数据 void HeapPop(Heap* php); //向下调整算法 void AdjustDown(int* a, int n, int parent); //判空 bool HeapEmpty(Heap* php); //堆顶元素 HeapDataType HeapTop(Heap* php); //元素个数 int HeapSize(Heap* php);heap.c的内容：
#include"heap.h" //堆的初始化 void HeapInit(Heap* php) { assert(php); php->a = NULL; php->size = 0; php->capacity = 0; } //堆的销毁 void HeapDestroy(Heap* php) { assert(php); free(php->a); php->a = NULL; php->size = 0; php->capacity = 0; } //交换数据 void Swap(HeapDataType* p1, HeapDataType* p2) { HeapDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整算法 void AdjustUp(HeapDataType* 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* php, HeapDataType x) { assert(php); //扩容 if (php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HeapDataType* tmp = (HeapDataType*)realloc(php->a, newcapacity * sizeof(HeapDataType)); 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); } //向下调整算法 //这边写int* 而不写HeapDataType* 是有意为之的 为以后堆排序作准备 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]) // 右孩子存在 右孩子<左孩子 //不能这么写 if (la[child + 1] < a[chid] && child + 1 < n ) //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在 { ++child; } //child就是小的那个孩子 //不关心到底是左孩子还是右孩子 小根堆：和小的孩子比较就可以了 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; child = parent * 2 + 1;//默认又算的是左孩子 } else { break; } } } //判空 bool HeapEmpty(Heap* php) { assert(php); if (php->size == 0) { return true; } else { return false; } } //删除堆顶数据 void HeapPop(Heap* php) { assert(php); assert(!HeapEmpty(php)); Swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); } //堆顶元素 HeapDataType HeapTop(Heap* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; } //元素个数 int HeapSize(Heap* php) { assert(php); return php->size; }test.c的内容：
void HeapSort(int* a, int n) { Heap hp; HeapInit(&hp); int i = 0; for (i = 0; i < n; i++) { HeapPush(&hp, a[i]); } while (!HeapEmpty(&hp)) { int top = HeapTop(&hp); a[i++] = top; HeapPop(&hp); } HeapDestroy(&hp); } int main() { int a[] = { 7,8,3,5,1,9,5,4 }; int sz = sizeof(a) / sizeof(a[0]); HeapSort(a, sz); return 0; }这样的堆排序其实也是可以的
但是有弊端！！！
第一个：得先有一个堆，太麻烦了
第二个：空间复杂度太高了，还有拷贝数据
堆排序——（2）
首先还是得建堆！！！
第一种方法：向上调整建堆
//建堆——向上调整建堆 int i = 0; for (i = 1; i < n; i++) { AdjustUp(a, i); }如果升序建小堆：
所以升序要建大堆
这边就是说排降序要建小堆
void HeapSort(int* a, int n) { //建堆——向上调整建堆 int i = 0; for (i = 1; i < n; i++) { AdjustUp(a, i); } //升序——建大堆 //降序——建小堆 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
第二种方法：向下调整建堆
//建堆——向下调整建堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); }
完整堆排序代码：
void HeapSort(int* a, int n) { //建堆——向下调整建堆 int i = 0; for (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; } }
向下调整的时间复杂度 
结点多，向下的调整次数少，结点少，向下的调整次数多
最后一层不需要调整，所以从倒数第二层开始计算
这里运用到了一个常见的数学方法——错位相减法
向上调整的时间复杂度
结点多，向上调整的次数多，结点少，向上调整的次数少
所以，向上调整建堆的效率和向下调整建堆的效率相比，向上调整要低得多
TopK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
数据多的话，数据存放在磁盘文件中
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}void PrintTopK(int k)
{
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int* kminheap = (int*)malloc(sizeof(int) * k);
if (kminheap == NULL)
{
perror("malloc error");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &kminheap[i]);
}
// 建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(kminheap, k, i);
}
int val = 0;
while (!feof(fout))
{
fscanf(fout, "%d", &val);
if (val > kminheap[0])
{
kminheap[0] = val;
AdjustDown(kminheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
printf("\n");
}好啦，小雅兰今天的学习内容就到这里啦，太摆烂了，还是要继续加油呀！！！文章来源：https://www.toymoban.com/news/detail-538320.html
文章来源地址https://www.toymoban.com/news/detail-538320.html
到了这里，关于堆排序+TopK问题——“数据结构与算法”的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
