目录
1.堆排序
2.top-k问题
1.堆排序
我们已经介绍了向上调整算法和向下调整算法建堆,可以建一个小堆或大堆,对于这种方式建立的大堆或小堆,我们只能选出最大的和最小的数,对于次大或次小的数,只能重新建堆,要想得到这组数据的降序或升序,只能不断建堆选取数据,但这种操作时间复杂度太高,每次建堆的时间复杂度为O(N)
如何建立一个有序的堆(以升序为例)?
- 升序建大堆,降序建小堆,使用向上调整算法或向下调整算法建大堆(小堆)
- 已经建成大堆,堆顶为这组数据中的最大元素,但堆中的数字并不是严格升序
- 堆顶元素和最后一个叶子节点交换,此时最后一个叶子节点为这组数据中的最大值,从堆顶向下调整选出次大的数,此时次大的数在根节点的位置,与倒数第二个叶子节点交换,此时倒数第二个叶子节点为这组数据中的次大值,后续依次类似处理
以以下数据为例
int a[] = { 4,1,7,8,15,34,19,27,25,65 };
step1:使用向上调整算法建大堆
这组数据逻辑上可以看作一棵完全二叉树的结构
向上调整建堆:向上调整算法从最后一个叶子节点开始调整,每次使一个元素到达其相对子节点较大的位置
第一次向上调整
第二次向上调整
第三次向上调整
第四次向上调整
第五次向上调整
第六次向上调整
第六次之后,所有的的节点都小于父节点,会进入循环,但不存在交换操作,循环在child<=0时结束;因此建大堆的操作完成,我们选出了最大的数,并存放在堆顶
step2:调整选数
1.堆顶元素和最后一个叶子节点交换,此时最后一个叶子节点为这组数据中的最大值,从堆顶向下调整选出次大的数,此时次大的数在根节点的位置
2.忽略最后一个存放最大值的节点,交换堆顶元素与倒数第二个叶子节点,此时倒数第二个叶子节点为这组数据中的次大值,堆顶元素向下调整选出第三大的数,此时第三大的数在根节点的位置
重复上述操作,就可以建立一个升序的堆
堆排序的本质:选择排序,利用堆的性质,依次选数,从后向前排
参考代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
typedef int HPDataType;
//交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{
assert(p1 && p2);
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
int maxchild = parent * 2 + 1;
while (maxchild < n)
{
//找到左右孩子中的较大者
if (maxchild + 1 < n && a[maxchild] < a[maxchild + 1])
{
maxchild = maxchild + 1;//更新最大孩子
}
if (a[parent] < a[maxchild])
{
Swap(&a[parent], &a[maxchild]);
//更新父子节点
parent = maxchild;
maxchild = parent * 2 + 1;
}
//当父子满足大堆关系时,不进行交换
else
{
break;
}
}
}
//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
//大堆
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapSort(HPDataType* a, HPDataType n)
{
//向上调整建大堆
int i = 0;
for (i = n - 1; i >= 0; i--)
{
AdjustUp(a, i);
}
//选数
i = 1;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjustDown(a, n - i, 0);
i++;
}
}
int main()
{
HPDataType a[] = { 4,1,7,8,15,34,19,27,25,65 };
int len = sizeof(a) / sizeof(a[0]);
HeapSort(&a, len);
//打印
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
return 0;
}
2.top-k问题
top-k问题:即求数据集合中前k个最大或者最小的元素 ,一般情况下数据量较大
如:专业前十名,世界500强,富豪榜前十名,游戏排行榜前十等
对于top-k问题,最简单直接的方式就是排序,但当数据量非常大,排序的方式就不可行,此时使用堆来解决,思路如下:
选前k个最大的:
1️⃣建大堆:
选出前k个最大的数,先建立一个大堆,使用堆排序,需要迭代k次,从后向前取前k个数即可,这种方法在N很大,k很小时,即在很大的数据集合中选出前几名,我们需要将这个数据集合先存储起来,可能出现内存存储不下,只能存储在磁盘中的情况
2️⃣ 建小堆:
- 用数据集合中的前k个数建立k个数的小堆
- 依次遍历后续N-k个数,与堆顶元素(最小的数)比较,若大于堆顶元素,则替换并向下调整到合适位置,向下调整后仍为k个数的小堆且堆顶元素为k个数中的最小数
- 重复上述操作,直到遍历完数据集合中的剩余元素
Note:
使用上述方法可以筛选出前k个最大的数,但选出来的这k个数是以小堆的方式存储的,但并不是有序排列的,如果需要其有序排列,使用上述堆排序的方法将其排序即可文章来源:https://www.uudwc.com/A/0kjZw/
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <time.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
//交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{
assert(p1 && p2);
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
int maxchild = parent * 2 + 1;
while (maxchild < n)
{
//找到左右孩子中的较大者
if (maxchild + 1 < n && a[maxchild] < a[maxchild + 1])
{
maxchild = maxchild + 1;//更新最大孩子
}
if (a[parent] < a[maxchild])
{
Swap(&a[parent], &a[maxchild]);
//更新父子节点
parent = maxchild;
maxchild = parent * 2 + 1;
}
//当父子满足大堆关系时,不进行交换
else
{
break;
}
}
}
//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
//大堆
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//创建数据文件
void CreateDataFile(const char* filename, int N)
{
FILE* fin = fopen(filename, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
srand(time);
for (int i = 0; i < N; i++)
{
fprintf(fin, "%d\n", rand()%100);//产生100以内的随机数
}
fclose(fin);
}
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//文件读取成功
//为堆开辟空间
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
//读取前k个数到为堆开辟的空间中
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
//前k个数建小堆.向上调整算法
for (int i = k - 1; i >= 0; --i)
{
AdjustUp(minHeap, i);
}
//依次访问后N-k个数
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
//出现比k个数中最小数大的数,替换并向下调整
if (val > minHeap[0])
{
minHeap[0] = val;
AdjustDown(minHeap, k, 0);
}
}
//打印前k个数
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.text";
int N = 100;
int k = 10;
//CreateDataFile(filename, N);
PrintTopK(filename, k);
return 0;
}
文章来源地址https://www.uudwc.com/A/0kjZw/