一.实现堆(以小堆为例)
1.heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//打印堆,用以测试
void HeapShow(Heap* hp);
// 对数组进行堆排序
void HeapSort(int* a, int n);
void AdjustDowna(HPDataType* a, int parent, int n);
2.heap.c
#include"heap.h"
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
hp->a = a;
hp->size = 0;
hp->capacity = n;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
free(hp->a);
hp->a = NULL;
free(hp);
}
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustUp(Heap* hp, int child)
{
assert(hp);
int parent = (child - 1) / 2;
while (child > 0)
{
if (child >=2 && ((child - 1 - 1) / 2 == parent) && (hp->a[child - 1] < hp->a[child]))
{
child--;
}
if (hp->a[child] < hp->a[parent])
{
Swap(&(hp->a[child]), &(hp->a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc failed");
return;
}
hp->a = tmp;
}
hp->a[hp->size] = x;
AdjustUp(hp, hp->size);
hp->size++;
}
void AdjustDown(Heap* hp, int parent)
{
assert(hp);
int child = parent * 2 + 1;
while (child < hp->size)
{
if (child + 1 < hp->size && hp->a[child + 1] < hp->a[child])
{
child++;
}
if (hp->a[child] < hp->a[parent])
{
Swap(&(hp->a[child]), &(hp->a[parent]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
hp->a[0] = hp->a[hp->size - 1];
AdjustDown(hp, 0);
hp->size--;
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
return hp->size == 0;
}
//打印堆,用以测试
void HeapShow(Heap* hp)
{
assert(hp);
int i = 0;
while (i < hp->size)
{
printf("%d ", hp->a[i]);
i++;
}
printf("\n");
}
二.堆排序
1.思想
堆排序,就是先将数据构建成堆,根据需要构建大堆或者小堆。
如果要排降序,就构建小堆。
如果要排升序,就构建大堆。
我们以降序为例:
在构建好小堆后,堆顶的数据就是最小的。
我们将堆顶数据与最后一个数据进行交换,然后把堆的最后一个位置排除在外(即它不参与后续的调整),对交换后的堆顶数据进行向下调整,如此,堆顶存放的就是次小的数据。
我们重复以上过程,那么就能依次选出最小的,次小的,次次小的······
2.代码
//向下调整
void AdjustDowna(HPDataType* a, int parent, int n)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
Swap(&(a[child]), &(a[parent]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
//构建小堆
for (int i = (n - 1) / 2; i >= 0; i--)
{
AdjustDowna(a, i, n);
}
int end = n - 1;
while (end > 0)
{
Swap(&(a[0]), &(a[end]));
n--;
AdjustDowna(a, 0, n);
end--;
}
}
三.TOPK问题
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
1.思路
当数据量非常大时,我们无法将所有数据进行堆排。
此时,我们可以构建一个k个容量的堆。
要找到最大的k个数据,我们就需要构建一个K个容量的小堆。
每次取出磁盘(或其它地方)的数据与堆顶数据进行比较,比堆顶数据大就进堆,然后向下调整。文章来源:https://www.toymoban.com/news/detail-469918.html
注意:不能构建成大堆,因为当堆顶的数据是最大的数据时,其它数据都无法进入堆。文章来源地址https://www.toymoban.com/news/detail-469918.html
2.代码
#include"heap.h"
//随机创造10000个数据
void CreateNData()
{
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand((unsigned int)time(NULL)) % 1000000;
if (i > n - 10)
{
x += 1000000;
}
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//找出TOPK
void PrintTopK(int k)
{
//打开上面写入数据的文件
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fout error\n");
return;
}
//创造堆
int* heap = (int*)malloc(sizeof(int) * k);
if (heap == NULL)
{
perror("malloc error\n");
return;
}
//取出前K个数据
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &heap[i]);
}
//构建小堆
for (int i = (k - 1) / 2; i > 0; i--)
{
AdjustDowna(heap, i, k);
}
//每次取出一个数据,与堆顶数据比较,比堆顶数据小就入堆,然后向下调整
int val = 0;
while (!feof(fout))
{
fscanf(fout, "%d", &val);
if (val > heap[0])
{
heap[0] = val;
AdjustDowna(heap, 0, k);
}
}
//打印出TOPK的数据
for (int j = 0; j < k; j++)
{
printf("%d ", heap[j]);
}
printf("\n");
}
int main()
{
CreateNData();
PrintTopK(10);
return 0;
}
到了这里,关于【数据结构】【堆】 堆排,TOPK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!