【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

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

目录

堆的概念及结构

​编辑

堆的实现 

实现堆的接口

堆的初始化

堆的打印

堆的销毁

获取最顶的根数据

 交换

堆的插入(插入最后)

向上调整(这次用的是小堆)

堆的删除(删除根)

向下调整(这次用的小堆)

堆排序

TOP-K问题


堆的概念及结构

如果有一个关键码的集合 K = { , , , ,},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0, 1 , 2…,则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

小根堆:父亲节点大于等于孩子节点

【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题,数据结构,数据结构

大根堆:父亲节点小于等于孩子节点 

【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题,数据结构,数据结构

堆的实现 

实现堆的接口

#define CRT_SECURE_NO_WARNING 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>

//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;


void AdjustUp(HPDataType* a, int child);

void AdjustDown(HPDataType* a, int n, int parent);

//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);

堆的初始化

//初始化
void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

堆的打印

void HeapPrint(HP* php)
{
	assert(php);

	//最后一个孩子下标为size-1
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

堆的销毁

//销毁
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

获取最顶的根数据

//获取根数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

 交换

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

堆的插入(插入最后)

先考虑扩容,将数据插到最后,再用向上调整法。

//插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//扩容
	if (php->size == php->capacity)//有效元素个数和容量是否相等
	{
		//相等的情况分两种:1.容量为0,先扩4个sizeof   2.容量占用满了,扩2个
		int newCapacity =php->capacity == 0 ? 4 : php->capacity * 2;
		//返回扩容后的内存新地址							//扩容后的新大小
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		//扩容后的新地址
		php->a = tmp;
		//新容量
		php->capacity = newCapacity;
	}

	//   php->size下标位置  先将x放最后,后面再调整
	php->a[php->size] = x;
	//   有效数据++
	php->size++;
	//   向上调整     //size-1为新插入数据的下标
	AdjustUp(php->a, php->size - 1);

}

向上调整(这次用的是小堆)

向上调整的前提:左右子树是堆 ,时间复杂度O(logN)

//向上调整                    //新插入的数据下标
void AdjustUp(HPDataType* a, int child)
{   
	//定义其父节点的下标
	int parent = (child - 1) / 2;
	//循环
	while (child > 0)
	{
		//如果子小于父就交换  (小堆)
		if (a[child] < a[parent])
		{
			//数值交换
			Swap(&a[child], &a[parent]);
			//下标
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的删除(删除根)

先判空,看下是否还有元素可以删除。根数据先和最后一个孩子交换位置,孩子再向下调整。

//删除
void HeapPop(HP* php)
{
	assert(php);
	//确保有元素可删
	assert(php->size > 0);

	//最后一个孩子和要删除的根交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//有效元素size减减,相当于删除了交换后的原来的根
	--php->size;

	//删除后向下调整
	AdjustDown(php->a, php->size, 0);

}

向下调整(这次用的小堆)

向下调整的前提:左右子树是堆 

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//n下标位置已经没有数了
	while (child < n)
	{
		//选小的孩子往上浮(小堆)
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//若小的孩子都小于父,则交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//交换后下来的数重新变成parent,继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
	}
}

堆排序

1. 建堆
升序:建大堆
降序:建小堆
2. 利用堆删除思想来进行排序
建堆:向上调整法建堆的时间复杂度:O(N*logN)
           向下调整法建堆的时间复杂度:O(N)
可以用堆删除思想向下调整法将栈顶和最后一个元素交换,依次将最大的次大的......往后放,就达到了升序排列。
void HeapSort(int* a, int n)
{
	//建堆  这里可以选建大堆还是小堆
	// 向下调整建堆
	// O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

TOP-K问题

TOP-K 问题:即求数据结合中前 K 个最大的元素或者最小的元素,一般情况下数据量都比较大
比如:专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了 ( 可能
数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前 K 个元素来建堆
k 个最大的元素,则建小堆
k 个最小的元素,则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K 个元素依次与堆顶元素比完之后,堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素

先创建一个包含有10000000个数的data.txt文本文件。

【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题,数据结构,数据结构

void CreateNDate()
{
	// 造数据
	int n = 10000000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 10000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

前k个建小堆(堆顶元素为k中最小),剩余n-k个依次和堆顶元素比较,比k大就插入堆中(插入堆插入向下调整法),完成后打印前k个元素。

void PrintTopK(const char* filename, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	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;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	// 前k个数建小堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}


	// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			// 替换你进堆
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}


	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);
}

假设k等于5,成功打印出前5个最大的数据

【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题,数据结构,数据结构

【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题,数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-754375.html

到了这里,关于【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Java 数据结构篇-实现堆的核心方法与堆的应用(实现 TOP-K 问题:最小 k 个数)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍      文章目录         1.0 堆的说明         2.0 堆的成员变量及其构造方法          3.0 实现堆的核心方法         3.1 实现堆的核心方法 - 获取堆顶元素 peek()         3.2 实现堆的核心方法 - 下潜 do

    2024年02月04日
    浏览(54)
  • 【数据结构】堆的应用——Top-K

    目录 前言: 一、Top-K问题描述: 二、不同解决思路实现: ①.排序法: ②.直接建堆法: ③.K堆法 总结:         上篇文章我们学习了二叉树的顺序存储结构,并且对于实际使用中所常用的顺序存储结构——堆的各个接口进行实现。这篇文章我们将对堆的实际应用进行更加

    2024年02月16日
    浏览(53)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(54)
  • 【数据结构】—堆排序以及TOP-K问题究极详解(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波: ルミネセンス—今泉愛夏      

    2024年02月08日
    浏览(48)
  • 数据结构与算法:堆排序和TOP-K问题

    朋友们大家好,本节内容来到堆的应用:堆排序和topk问题 我们在c语言中已经见到过几种排序,冒泡排序,快速排序(qsort) 冒泡排序的时间复杂度为O(N 2 ),空间复杂度为O(1);qsort排序的时间复杂度为 O(nlogn),空间复杂度为O(logn),而今天所讲到的堆排序在时间与空间复杂度上相

    2024年03月08日
    浏览(62)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(47)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(43)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • 【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录 堆排序 第一种  ​编辑 第二种  TOP-K问题 建堆的时间复杂度 向下调整建堆的时间复杂度:  向上调整建堆的时间

    2024年01月21日
    浏览(61)
  • 堆的实现,画图和代码分析建堆,堆排序,时间复杂度以及TOP-K问题

    如果有一个关键码的集合K = {k 0 ,k 1 ,k 2 ,…,k n-1 },把它的所有元素按 完全二叉树 的顺序存储方式存储在一个一维数组中,并满足:k i =k 2*i+1 且 =k 2*i+2 (k i =k 2*i+1 且 =k 2*i+2 ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫

    2024年02月04日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包