当前位置：首页 > news >正文

【数据结构】堆排序与TOP-K问题

news 来源：原创 2024/9/20 3:47:45

🌈个人主页：Yui_
🌈Linux专栏：Linux
🌈C语言笔记专栏：C语言笔记
🌈数据结构专栏：数据结构

文章目录

1.堆排序
- 1.1 建堆
- 1.2 利用堆删除思想来进行排序
- 1.3 堆排序的时间复杂度
2.TOP-K问题

1.堆排序

堆排序就是利用堆的思想进行排序，总共分为两个步骤：

1.1 建堆

升序：建大堆
降序：建小堆
利用向下调整建堆
提问：为什么向下调整可以建堆
回答：
向下调整的关键就除了要调节的地方不对，其下方都为正确的堆。
以下图为例：以10为根的左右子树，都满足小堆（堆）的性质，只有根节点不满足时，因此只需将根节点往下调，整合到合适的位置就可以了。

为了我只有由后往前向下调整就可以了，第一次要传的参数就是最后一个节点的父节点。然后依次传入前面是位置就可以了。

#include <stdio.h>void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = 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 = child + 1;}if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int main()
{int arr[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 };//初始化一个小堆int n = sizeof(arr) / sizeof(arr[0]);for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(arr, n, i);//通过向下调整建立大堆}for (int i = 0; i < n; ++i){printf("%d ", arr[i]);}return 0;
}
//打印结果：
/*
100 70 60 65 32 50 8 3 7 4 2 5 6
*/

1.2 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整就可以完成堆排序。
提问：为什么升序需要建大堆呢？
回答：堆排序的本质是选择排序，每次都要选择一个最大的数到数组的最后一位，那么问题就变成了如何选择最大的数到数组最后一位，要找出堆中最大数就必须要用到大堆，因为大堆中最大的数就在堆堆顶，通过一次次的选择就可以将数组排序。
下面是画图解释：
利用堆删除思想来进行排序

#include <stdio.h>void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = 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 = child + 1;}if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int main()
{int arr[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 };int n = sizeof(arr) / sizeof(arr[0]);for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(arr, n, i);}//排序for (int end = n - 1; end >= 0; --end){swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);}for (int i = 0; i < n; ++i){printf("%d ", arr[i]);}return 0;
}
//打印结果：
/*
2 3 4 5 6 7 8 32 50 60 65 70 100
*/

1.3 堆排序的时间复杂度

O(N*logN)

2.TOP-K问题

TOP-K问题：即求数据结合中前k个最大元素或者最小元素，一般情况下数据量都比较大。
比如：专业前10名，时间500强、游戏中的前100的玩家。
对于TOP-K问题，能想到的最简单的方式就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据不能一下子全部加载到内存中）。最佳的方式就是用堆来解决，基本思路如下：

用数据集合前K个元素来建堆

前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完后，堆中剩余的K个元素就是所求得前K个最小或者最大的元素。

下面我们将找出1000000个数中最大的10个数，为此我们需要建造一个大小为10的小堆。
主要步骤：

创建1000000个随机数，数值范围[0,999999]
创建一个大小为10的小堆
开始进堆，如果当前数值大于堆顶数据，就将堆顶数值替换为当前数值，然后向下调整，让大的数下沉。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = 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 = child + 1;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int main()
{int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand((unsigned int)time(NULL));//生成随机种子for (int i = 0; i < n; ++i){a[i] = rand() % 1000000;//数据范围：[0,999999]}//选出数据中最大的10个数,建小堆//为了证明确实可以找到，我们需要自己设置10个大于范围的数，如果最后被找到就说明正确a[5] = 1000000 + 1;a[55] = 1000000 + 2;a[99] = 1000000 + 3;a[1001] = 1000000 + 4;a[123] = 1000000 + 5;a[124] = 1000000 + 6;a[18] = 1000000 + 7;a[1111] = 1000000 + 8;a[999] = 1000000 + 9;a[100] = 1000000 + 10;int heap[10] = { 0 };for (int i = 0; i < n; ++i){if (a[i] > heap[0]){heap[0] = a[i];AdjustDown(heap, 10, 0);}}for (int i = 0; i < 10; ++i){printf("%d ", heap[i]);}return 0;
}
//打印结果：
/*
1000001 1000002 1000003 1000004 1000009 1000006 1000005 1000007 1000008 1000010
*/