向下调整算法
首先声明这个算法的使用条件，该算法适用于除了堆顶外的其他部分都满足小堆或大堆的条件时，可以使用，简单来说就是pop堆顶的时候可以使用
使用的原理也相当简单，假设我们这里是小堆，那么堆顶元素被弹出，此时堆中第二小的元素一定是这个堆顶元素的儿子，那么我们就让堆的最后一个叶子来充当这个新的堆顶，这样可以在保持堆整体的构造不变的前提下还能把堆顶元素弹出，紧接着就让这个堆顶元素和下面的儿子进行比较，谁小谁就是新的堆顶，进行交换后第二小的元素就产生了，当然，如果树的高度很高，那么交换后可能需要继续交换，知道这个叶子回到最后一层，这个过程也是可以借助循环实现的，借助这个向下调整算法就可以把堆顶元素弹出的同时还能变成一个新堆，不断的找出最小的值或最大的值
那么下面我们来实现这个算法
void AdjustDown(HP* php, int n, int parent)
{
assert(php);
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && php->a[child + 1] < php->a[child])
{
child++;
}
if (php->a[child] < php->a[parent])
{
Swap(&php->a[child], &php->a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(HP* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php, php->size, 0);
}
堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
- 建堆
升序：建大堆
降序：建小堆 - 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
下面说明堆的另外一个作用，可以用来堆排序
首先说明堆排序的原理：假设现在这里有10个数字，现在把这10个数字建成小堆，那么堆顶的元素就是这10个数字的最小值，再让该数字和最后一个元素呼唤位置，这样最小值就到了最后一个位置，再进行向下调整算法可以调整出第二小的元素，按照上方的流程重新来一次，就能弄出新的数字，这样下去就可以实现降序排列的功能
具体操作流程如下
void HeapSort(HPDataType* a, int size)
{
assert(a);
//建堆
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, size, i);
}
//排序
int end = size - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
这样的排序也是有效的
那么堆排序好在哪里？从时间复杂度来看，堆排序的时间复杂度只有O(NlogN)，整体来看效率还是可以的
TopK
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
比特就业课
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(int* a, int n, int k)
{
// 1. 建堆--用a中前k个元素建堆
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
堆真正强大的功能其实是强大在从很大一个量级的数字中要找出其中最大或最小的10个，假设这个数字是一亿甚至十亿，那么如果我们还采用的是正常的排序来看，那么整个过程就会相当麻烦，把这些数字全部排序再找最大或最小的几个，这个过程消耗的时间和空间复杂度是不可计算的，甚至计算机没有足够的内存供你建立如此庞大的空间
因此堆可以很好的解决这个问题，堆的功能主要体现在它可以筛选出你要的数据，下面介绍topk的原理
假设我们现在有10000个数字，我们要从中找到最大的5个，那么如何用堆来进行实现？
首先，我们把前五个数字建一个堆，假设我们要找的是最大的五个数，那么我们就建立小堆，然后让后面的数字依次从堆顶看能不能进入堆中，假设这个数字大于堆顶元素，那么就让这个元素称为堆顶元素，再进行向下调整，接着让下一个元素和堆顶比较...
按这样的想法实施下来，就可以使得堆中的元素是所有数字里面最大的五个元素，这样就能实现目标
==下面就来模拟实现这个过程==
首先，我们要获取到这10000个数据，下面展示获取数据量的一种途径
void CreateData()
{
int n = 10000;
srand(time(0));
FILE* pf = fopen("test.txt", "w");
if (pf == NULL)
{
perror("fopen fail");
return;
}
for (int i = 0; i < n; i++)
{
int x = rand() % 10000;
fprintf(pf, "%d\n", x);
}
fclose(pf);
}
获取了信息下面开始实现topk的功能
void PrintTopK()
{
Heap hp = {
0,0,0 };
HeapCreate(&hp,hp.a,4);
FILE* pf = fopen("test.txt", "r");
if (pf == NULL)
{
perror("fopen fail");
return;
}
int* kmaxheap = (int*)malloc(sizeof(int) * 5);
if (kmaxheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < 5; i++)
{
fscanf(pf, "%d", &kmaxheap[i]);
HeapPush(&hp, kmaxheap[i]);
}
int val = 0;
while (!feof(pf))
{
fscanf(pf, "%d", &val);
if (val > kmaxheap[0])
{
kmaxheap[0] = val;
AdjustDown(kmaxheap, 5, 0);
}
}
for (int i = 0; i < 5; i++)
{
printf("%d ", kmaxheap[i]);
}
}
