【数据结构】【堆】 堆排,TOPK问题

这篇具有很好参考价值的文章主要介绍了【数据结构】【堆】 堆排,TOPK问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.实现堆(以小堆为例)

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

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】堆排序和TOPK问题

     😽 PREFACE 🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝 📢系列专栏:数据结构 🔊本专栏主要更新的是数据结构部分知识点 💪 种一棵树最好是十年前其次是现在 目录 0.利用堆的实现进行排序 1.堆排序 1.1 建堆 ​编辑  1.1.1 向上建堆 1.1.2 向下建堆 1.2 时间复杂度分析 1.3 堆排序

    2024年02月01日
    浏览(32)
  • 【数据结构】堆的应用-----TopK问题

    目录 一、前言 二、Top-k问题   💦解法一:暴力排序 💦解法二:建立N个数的堆 💦解法三:建立K个数的堆(最优解) 三、完整代码和视图  四、共勉 在之前的文章中,已经详细的讲解了二叉树、堆、堆排序。那么关于堆还有一个比较有意思的题,就是TopK问题。 如果对堆

    2024年02月07日
    浏览(46)
  • 数据结构——堆排序的topk问题

    呀哈喽,我是结衣 今天给大家带来的堆排序的topk问题。topk就是在许多数中,找出前k个大的数,可能是几十个数,也可能是几千万个数中找。今天我们将要在1000000(一百万)个数中找出前10大的数。 C语言文件的读写 建堆 向下调整排序 随机数的产生 ps 向下调整和向上调整的

    2024年02月04日
    浏览(35)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(58)
  • 【数据结构】堆排序与TopK问题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言  1.堆的概念和结构 2.堆的实现 2.1向上调整算法 2.2向下调整算法 2.3堆的创建 2.4建堆时间复杂度 2.5堆的

    2024年02月07日
    浏览(39)
  • 堆排序+TopK问题——“数据结构与算法”

    各位CSDN的uu们你们好呀,好久不见,停更了很长一段时间吧,最近小雅兰会开始慢慢更新起来的,下面,就进入小雅兰今天的分享的知识点吧,让我们一起进入堆的世界!!! 堆排序——(1) heap.h的内容: heap.c的内容: test.c的内容: 这样的堆排序其实也是可以的 但是有弊

    2024年02月13日
    浏览(48)
  • 玩转堆排序以及Topk问题——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 目录 堆排序  建堆  建堆的时间复杂度 Topk问题 学习了二叉树以及堆,今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。 在学习开始我们先来回顾一下上篇博客中我们提到的堆,在实现堆时我们要进行向上调整或向下调

    2024年02月07日
    浏览(35)
  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(42)
  • 数据结构之树(Topk问题, 链式二叉树)

    取N个数中最大(小)的前k个值,N远大于k 这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆 时间复杂度O(k) 之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整 时间复杂度(N-k)*log(N) 总共的时间复杂度为O(N*log(N)) 用数组

    2024年03月15日
    浏览(41)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包