上次才讲完堆的相关问题:二叉树顺序结构与堆的概念及性质(c语言实现堆
那今天就接着来进行堆的主要两方面的应用:堆排序和TOP-K问题
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
int father = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[father])
{
Swap(&a[child], &a[father]);
//更新下标
child = father;
father = (father - 1) / 2;
}
else
{
break;//一旦符合小堆了,就直接退出
}
}
}
void AdjustDown(HPDataType* a, int n, int father)
{
int child = father * 2 + 1;//假设左孩子大
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[child] > a[father])
{
Swap(&a[child], &a[father]);
father = child;
child = father * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* arr, int n)//升序
{
//先建大堆
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
int a = n - 1;
while (a > 0)
{
//此时最大的是堆顶,堆顶跟最后一个交换
Swap(&arr[0], &arr[a]);
//现在最大的已经在最后了,不考虑它,把新塔顶降下来,重新编程大堆
AdjustDown(arr, a, 0);
a--;
}
}
int main()
{
int arr[]= { 4,6,2,1,5,8,2,9 };
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
printf("%d ", arr[i]);
}
printf("\n");
HeapSort(arr, sizeof(arr) / sizeof(int));
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
printf("%d ", arr[i]);
}
}
结果:
仅仅该那一部分:
void HeapSort(int* arr, int n)//升序
{
//先建大堆
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//}
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int a = n - 1;
while (a > 0)
{
//此时最大的是堆顶,堆顶跟最后一个交换
Swap(&arr[0], &arr[a]);
//现在最大的已经在最后了,不考虑它,把新塔顶降下来,重新编程大堆
AdjustDown(arr, a, 0);
a--;
}
}
对于一个具有n个节点的完全二叉树来说,最后一个非叶子节点的下标是(n-1-1)/2,也就是说,从最后一个非叶子节点开始,依次向上调整每个节点,就可以建立一个大堆
相比于向上调整,向下调整的好处:时间复杂度低
建堆的时间复杂度为 O(n),排序过程的时间复杂度为 O(n log n)(建堆的时间复杂度为 O(n),而对堆进行排序的过程中,需要进行 n-1 次堆调整操作,每次堆调整的时间复杂度为 O(log n)。因此,排序过程的时间复杂度为 O(n log n))
TOP-K问题:求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大 对于Top-K问题,能想到的最简单直接的方式就是排序,然后直接取。 但是:如果数据量非常大,排序就不 太可取了,最佳的方式就是用堆来解决,基本思路如下:
void CreateData()//用来创建有随机数的文件的进行检测
{
int N = 1000;
srand(time(0));
FILE* f = fopen("data.txt", "w");
for (int i = 0; i < N; i++)
{
int a = (rand()) % 10000;
fprintf(f,"%d\n", a);
}
fclose(f);
}
void PrintTopK(int k)//前k个大的
{
//先读文件
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen file");
return -1;
}
int* a = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)//建立元素k的小堆
{
fscanf(fout, "%d", &a[i]);//把文件里的前k个数字写入数组里
AdjustUp(a, k);
}
//如果有比堆顶大的,就进来
int n = 0;
while (fscanf(fout, "%d", &n) != EOF)//读到文件读完就停止
{
if (n > a[0])
{
a[0] = n;
AdjustDown(a, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
printf("\n");
fclose(fout);
}
int main()
{
PrintTopK(5);
return 0;
}
结果如下:
那这次堆的两大应用就先到这里啦,到此二叉树顺序结构部分的知识也已经分享完毕了。感谢大家的支持,希望能帮助到大家!!!