堆的应用——堆排序 & TOPK问题
堆的应用
我们已经学完堆了,那堆有啥应用呢?
3.4.1 堆排序
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
建堆
升序:建大堆
降序:建小堆
利用堆删除思想来进行排序
这就是堆排序的两个步骤。
首先,简单解释一下为啥升序建大堆,降序建小堆:
拿升序来说,其实建小堆也不是不能搞,只是不太好。
为什么呢?
现在这有一个数组,如果升序,建小堆可以首先可以得到最小的数据,🆗,就是堆顶元素。
那像得到下一个次小的怎么办,把第一个删除了,重新把剩余元素建堆?
那把第一个删除了,往哪保存啊。
再开新空间?再搞个数组保存?
也可以,但它的空间复杂度就是O(N)了。
再一个,删除之后,像选出次大的,我们是不是还要重新建堆啊,而且把第一个删除之后原来堆里的关系也就全乱了。
那建堆的时间复杂度是O(N),还是向下调整建堆比较优的。而且这样搞我们建一次堆才能选出来一个数,如果一次选一个数我们直接遍历也能搞定,没必要建堆了,反而麻烦了。
那其实降序也是这样。
所以好的做法是什么呢?
我们就换一下:升序我们就建大堆,降序建小堆。
好的,那我们接下来就还以升序为例,给大家讲一下完整的一个堆排序的过程:
假设我们现在要对这样一组数据进行堆排序:
int arr[] = {27,15,19,18,28,34,65,49,25,37};
堆排序呢,我们只需给数组和元素个数就行了:
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
接下来我们就来实现一下HeapSort函数:
首先第一步建堆(注意这里是直接将数组改变成堆),升序我们建大堆
选择向下调整建堆更优:
void HeapSort(int* arr, int n)
{
//建堆:升序大堆,降序小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
}
堆建好了,下一步是利用堆删除思想来进行排序,什么意思呢?解释一下:
将上面的数组建成大堆应该是这样的:
那现在堆顶的数据就是最大的,现在想排升序,怎么搞?
什么叫利用堆删除的思想呢?
🆗,现在堆顶数据是最大的,我们将堆顶数据与最后一个交换:
交换之后怎么办,最大值已经处在最终应该待的位置了,那最后一个数我们就不用管了,也不用开新空间去保存它。
下次调整数据个数我们传n-1就行了:
AdjustDown(arr, n-1, i);
接下来只需对前n-1个数进行调整,还需要重新建堆吗?
是不是只需要进行一个向下调整就OK了啊。因为此时对于前n-1个数组成的这个完全二叉树来说,它的左右子树都是堆,那我们就可以用向下调整算法,调整之后就是前n-1个数建成的堆了,就能拿到次大的数即此时堆顶的数据。
依次循环往复,什么时候结束?
当堆中只剩一个数据时结束,这时就排好了。
为什么这种方法更好呢?
之前那种方法我们除了要保存删除的数据之外,每次选一个数就要重新建一次堆,效率很低。
但是这种方法,我们不需要开新空间,而且每次选一个数只需进行一次向下调整即可,向下调整最多只需调整高度次,时间复杂度为log2(N),就快了不少。
所以说,这才是真正的堆排嘛!
🆗,那思路理清了,接下来来写代码:
//堆排序
void HeapSort(int* arr, int n)
{
//建堆:升序大堆,降序小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int count = n - 1;
while (count > 0)
{
swap(&arr[0], &arr[count]);
AdjustDown(arr, count, 0);
count--;
}
}
堆排序就实现好了。
简单补充一下大家可能有疑惑的地方:
上面不是说堆中只有一个数据就该结束了嘛,是的,只有一个的话其它的元素都排好了,那最后这一个自然也就在正确位置了。
那为啥循环结束条件是:while (count > 0)呢?
因为调整之后还没完,还要等下一轮循环进去之后交换完它们的位置才是正确的。
当只剩两个数据count=2时,调整完,count- -变成1,再次进入循环,先交换,将较大的那个换到第二个位置,那这时其实已经排好序了,不过接着下来有调整一次,不过这个没关系,只有一个数据,调不调都一样,然后count- - 变成0,循环结束。
在这里我们拿升序给大家举例了,那其实降序也是一样的,换成小堆就行了。
堆排序的时间复杂度时O(N*log2N)
大家可以算一算。
最后,写好了那我们来测试一下:
没有问题。
3.4.2 TOP-K 问题
其实在上面我们已经提到过TOP-K问题了,再来回顾一下:
TOP-K问题:即求数据集合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序。
那其实用我们这篇文章前面所学的东西也能解决TIOP-k问题:
加入现在要在N个数中找出最大的前K个,怎么做?
建立一个N个数的大堆,pop(删除堆顶元素)K次,依次取堆顶数据。
如果N比较小的情况下,我们确实可以这样搞,而且效率也不算特别差。
但是:
不管是排序也好,还是用刚才介绍的这种方法,都会面临一个问题:
上面提到top-k问题一般数据量都比较大。
如果数据量非常大,排序或者将所有数据建堆就不太可取了(可能数据都不能一下子全部加载到内存中)。
比如现在有100亿个整数,换算一下差不多40G,电脑内存一般情况都放不下,除非搞文件里放到磁盘上。
那这时前面提到的方法就不行了。
所以下面我们提供一个新思路:
用数据集合中前K个元素来建堆
取前k个最大的元素,则建小堆
取前k个最小的元素,则建大堆
用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素,然后向下调整,最终我们想要的最大或最小的K个数据,就在这个K个数的堆中
🆗,那为什么这么做就能取出TOP-k的数据呢?简单解释一下:
我们以取前K个最大的数据为例。
那我们要以前K个数据建小堆,然后拿后面的数据依次和堆顶数据进行比较,那小堆的话堆顶的数最小的,后面比较大的数就会替换堆顶数据,然后调整之后这些大的数据还是跑到了堆的下面,所以即使先遇到了最大的数据,也不会堵在堆顶使得其它次大的数据进不来,因为大的总是在下面,这样一直调整一直交换,最后这个堆中保留的就是最大的k个数。
那我们来算一下该算法的时间和空间复杂度:
时间复杂度:
首先k个数建堆,然后假设后面每个数比较都要替换和进行向下调整,那就是k+(N- k ) x log2K,那数据很多的情况下,k相对于N就很小了。
所以可以认为时间复杂度是O(N*log2K)。
空间复杂度:
那就是O(K),我们只创建了一个k个数的堆嘛。
那我们接下来就举个栗子,实现一下这个算法:
这里我们就不搞特别多的数据,放在文件里搞了,只是给大家演示一下,重点还是让大家理解一下这个过程。
我们这里就给一个数组模拟一下这个过程:
int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};
搞一个数组,随便给一些值,现在我们找出最大的5个。
首先第一步,找大的值,应该建小堆:
我们之前向下调整是建大堆的,建小堆的话把大于小于号改变一下就行了。
//前5个数建小堆
int minHeap[5];
for (int i = 0; i < k; i++)
{
minHeap[i] = arr[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, k, i);
}
接着第二步:
拿剩余元素依次与堆顶数据进行比较,大于堆顶数据则替换,然后向下调整。
for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
{
if (arr[j] > minHeap[0])
{
minHeap[0] = arr[j];
AdjustDown(minHeap, k, 0);
}
}
两个步骤,就完成了:
void test_topk()
{
int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};
//找出最大的5个
//前5个数建小堆
int k = 5;
int minHeap[5];
for (int i = 0; i < k; i++)
{
minHeap[i] = arr[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, k, i);
}
for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
{
if (arr[j] > minHeap[0])
{
minHeap[0] = arr[j];
AdjustDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
printf("\n");
}
验证一下:
🆗,最大的前5个就出来了。
不过我们测试的数据比较少,其实数据量大也是一样的逻辑,只不过比较和调整的次数多一点罢了。
4. 堆及其应用对应 源码
4.1 heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef int HPDataType;
typedef struct heap
{
HPDataType* arr;
int size; //数组大小
int capacity; //容量
}HP;
// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size);
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//打印
void HeapPrint(HP* php);
//向上调整
void AdjustUp(HPDataType* arr, int child);
//插入数据,并保证它仍然是一个堆
void HeapPush(HP* php, HPDataType x);
//向下调整
void AdjustDown(HPDataType* arr, int size, int parent);
//删除堆顶元素,并确保删除之后还是一个堆
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
int HeapSize(HP* php);
// 堆的判空
bool HeapEmpty(HP* php);
void swap(HPDataType* e1, HPDataType* e2);
4.2 heap.c
#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"
// 堆的构建
void HeapCreate(HP* php, HPDataType* arr, int size)
{
assert(php);
php->arr = (HPDataType*)malloc(sizeof(HPDataType) * size);
if (php->arr == NULL)
{
perror("malloc fail");
exit(-1);
}
memcpy(php->arr, arr, sizeof(HPDataType) * size);
php->capacity = php->size = size;
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->arr, size, i);
}
}
//初始化堆
void HeapInit(HP* php)
{
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}
//销毁堆
void HeapDestory(HP* php)
{
assert(php);
free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
//交换
void swap(HPDataType* e1, HPDataType* e2)
{
HPDataType tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{
assert(arr);
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[child] > arr[parent])
{
swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入数据,并保证它仍然是一个堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//判断堆是否满,满的话进行扩容
if (php->size == php->capacity)
{
int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
php->size++;
//调整
AdjustUp(php->arr, php->size - 1);
}
//打印
void HeapPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->arr[i]);
}
printf("\n");
}
向下调整(大堆)
//void AdjustDown(HPDataType* arr, int size, int parent)
//{
// assert(arr);
// int child = parent * 2 + 1;
// //没有右孩子,说明是个叶子,循环结束
// while (child < size)
// {
// //得出较大的那个孩子,有可能有右孩子,但没有左孩子
// //所以加上child + 1 < size
// if (child + 1 < size && arr[child + 1] > arr[child])
// {
// child++;
// }
// //如果孩子大于父亲,就交换
// if (arr[parent] < arr[child])
// {
// swap(&arr[child], &arr[parent]);
// parent = child;
// child = parent * 2 + 1;
// }
// //如果小于孩子,调整结束
// else
// {
// break;
// }
// }
//}
//向下调整(小堆)
void AdjustDown(HPDataType* arr, int size, int parent)
{
assert(arr);
int child = parent * 2 + 1;
//没有右孩子,说明是个叶子,循环结束
while (child < size)
{
//得出较大的那个孩子,有可能有右孩子,但没有左孩子
//所以加上child + 1 < size
if (child + 1 < size && arr[child + 1] < arr[child])
{
child++;
}
//如果孩子小于父亲,就交换
if (arr[parent] > arr[child])
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
//如果小于孩子,调整结束
else
{
break;
}
}
}
//删除堆顶元素,并确保删除之后还是一个堆
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
//向下调整
AdjustDown(php->arr, php->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->arr[0];
}
// 堆的数据个数
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
// 堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
4.3 test.c
#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"
void test1()
{
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
HP hp;
HeapInit(&hp);
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
HeapPush(&hp, arr[i]);
}
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDestory(&hp);
}
void test2()
{
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
HP hp;
HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0]));
HeapPrint(&hp);
HeapDestory(&hp);
}
//堆排序
void HeapSort(int* arr, int n)
{
//建堆:升序大堆,降序小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int count = n - 1;
while (count > 0)
{
swap(&arr[0], &arr[count]);
AdjustDown(arr, count, 0);
count--;
}
}
void testHeapSort()
{
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
}
void test_topk()
{
int arr[] = {0,3,4,32,56,787,232,1,23,44,23,78,45,16,37,36,843,28};
//找出最大的5个
//前5个数建小堆
int k = 5;
int minHeap[5];
for (int i = 0; i < k; i++)
{
minHeap[i] = arr[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, k, i);
}
for (int j = k; j < sizeof(arr) / sizeof(arr[0]); j++)
{
if (arr[j] > minHeap[0])
{
minHeap[0] = arr[j];
AdjustDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
printf("\n");
}
int main()
{
//test1();
//test2();
//testHeapSort();
test_topk();
return 0;
}
- 点赞
- 收藏
- 关注作者
评论(0)