【数据结构】堆的实现,堆排序以及TOP-K问题

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

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

目录

1.堆的概念及结构

2.堆的实现

2.1初始化堆

2.2销毁堆

2.3取堆顶元素

2.4返回堆的大小

2.5判断是否为空

2.6打印堆

2.7插入元素

2.8堆的向上调整

2.9弹出元素

2.10堆的向下调整

3. 建堆时间复杂度

4. 堆的应用

4.1 堆排序

4.2 TOP-K问题


1.堆的概念及结构

堆是一种数据结构,它是由一组元素组成的,并按照一定的规则进行排序和访问。堆可以看作是一个完全二叉树,其中每个节点的值都大于或等于其子节点(对于最大堆)小于或等于其子节点(对于最小堆)。堆通常用来解决具有优先级的问题,例如找到最大或最小的元素。

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

 堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

2.堆的实现

这里写的是小根堆,大根堆可以在小根堆的基础上稍作修改。下面是堆要实现的一些接口函数:

//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//插入元素
void HeapPush(HP* php, HPDataType x);
//堆向上调整算法
void AdjustUp(HP* php, int x);
//弹出堆顶元素
void HeapPop(HP* php);
//堆向下调整算法
void AdjustDwon(HPDataType* a, int size, int x);
//取堆顶元素
HPDataType HeapTop(HP* php);
//返回堆的大小
int HeapSize(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//打印堆
void HeapPrint(HP* php);

堆的定义:

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

对于一些简单的接口函数,我们就不详细介绍了,在堆中,我们主要要学习的是向上调整算法和向下调整算法。这两个函数分别在插入元素和弹出元素的时候会调用。

2.1初始化堆

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

2.2销毁堆

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

2.3取堆顶元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

2.4返回堆的大小

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

2.5判断是否为空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

2.6打印堆

void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

2.7插入元素

向堆中插入一个元素,我们可以将这个元素插入到堆的尾部,因为堆的实际存储结构是一个数组,我们可以将元素放到数组末尾,但如果仅仅是插入到数组末尾的话,会将堆的结构给破环,我们还需要调用一个向上调整的函数,来调整各个节点间的大小关系。

在插入之前,需要判断堆的容量是否足够,如果堆的容量已满,需要扩容,这里每次扩容实在原来的基础上扩2倍。

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->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);//向上调整
	php->size++;
}

2.8堆的向上调整

在上面插入元素的过程中,我们已经使用了堆的向上调整算法,下面,我们来看看怎么实现这个向上调整算法吧:

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。

图示过程:

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

void AdjustUp(HPDataType* a, int x)
{
	int child = x;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}

代码分析: 

  1. 初始化变量child为节点x,parent为其父节点的索引,也即 (child - 1) / 2。
  2. 进入一个循环,该循环会一直执行直到节点x上浮到合适的位置或者到达堆顶。
  3. 在循环中,判断节点x的值是否小于其父节点的值,若成立则交换两者的值。
  4. 若节点x的值不小于父节点的值,则跳出循环,因为此时堆的性质已满足。
  5. 更新child和parent的值,将child更新为parent,parent更新为其父节点的索引,也即 (child - 1) / 2。
  6. 重复步骤3-5,直到节点x的值大于或等于其父节点的值,或者到达堆顶。

2.9弹出元素

弹出元素就是将堆顶的元素给删除,但我们不能直接进行删除,这样会将堆的结构给破坏,正确的方法是先将堆顶的元素和最后的元素进行交换,这样保证的首元素的左子树和右子树依然是堆的形态,然后将size自减,最后调用一个堆的向下调整函数。

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	AdjustDwon(php->a, php->size, 0);
}

2.10堆的向下调整

堆的向下调整:每次将父节点和左右孩子的较小值进行交换(小根堆),不断地更新父节点的孩子节点的值。

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

void AdjustDwon(HPDataType* a, int size, int x)
{
	int parent = x;
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}
  1. 初始化变量parent为节点x,child为其左子节点的索引,也即 parent * 2 + 1。
  2. 进入一个循环,该循环会一直执行直到节点x下沉到合适的位置或者没有子节点。
  3. 在循环中,首先判断节点x是否有右子节点,并且右子节点的值小于左子节点的值,如果成立则将child更新为右子节点的索引。
  4. 接着判断节点x的值是否大于其子节点的值,若成立则交换两者的值。
  5. 若节点x的值不大于子节点的值,则跳出循环,因为此时堆的性质已满足。
  6. 更新parent和child的值,将parent更新为child,child更新为parent的左子节点的索引,也即 parent * 2 + 1。
  7. 重复步骤3-6,直到节点x的值小于或等于其子节点的值,或者没有子节点。

3. 建堆时间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

向下调整:

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

因此:向下调整建堆的时间复杂度为O(N)。

向上调整:

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

 因此:向上调整建堆的时间复杂度为N*logN;

4. 堆的应用

4.1 堆排序

利用堆排序数组并打印出来:

void testHeapSort()
{
	HP hp;
	HeapInit(&hp);

	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	//释放内存
	HeapDestory(&hp);
}
int main()
{
	testHeapSort();
	return 0;
}

输出结果:

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

 但是,使用这种方法是不是有点复杂了呢?我们要进行堆排序,还得先写一个堆的数据结构,当然并不是这样的,我们可以将代码进行修改,在原数组上进行建堆:

思路:

对于在原数组上进行建堆,我们可以使用两种方式:

第一种是向上建堆,向上建堆的时间复杂度是 O(N*logN),我们不推荐使用这种方法。

第二种是向下建堆,它的时间复杂度是O(N),它的效率比向上建堆要高。我们推荐使用向下建堆。

还有一个比较让人难以理解的一点是:如果要进行升序,我们要建大堆,如果要进行降序,我们要建小堆。

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void HeapSort(int* a, int n)
{
	//从倒数第一个非叶子节点开始调
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);//向下调整建堆
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);//向下调整[0,end]的元素
		--end;
	}
}
int main()
{
	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a,n);//堆排序
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

4.2 TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1. 用数据集合中前K个元素来建堆

  • 前k个最大的元素,则建小堆
  • 前k个最小的元素,则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

实际应用:在10000000个随机数中找出前十个最大的数字

void AdjustDwon(int* a, int size, int x)
{
	int parent = x;
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}

void PrintTopK(int* a, int n, int k)
{
	int* KMaxHeap = (int*)malloc(sizeof(int) * k);
	assert(KMaxHeap);
	for (int i = 0; i < k; i++)
	{
		KMaxHeap[i] = a[i];
	}
	//建小根堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(KMaxHeap, k, i);
	}
	//依次比较a数组中剩余的元素
	for (int i = k; i < n; i++)
	{
		if (a[i] > KMaxHeap[0])
		{
			KMaxHeap[0] = a[i];
		}
		AdjustDwon(KMaxHeap, k, 0);
	}
	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", KMaxHeap[i]);
	}
}
void testTopK()
{
	srand(time(0));
	int n = 10000000;
	int* a = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % n;//a[i]的范围[1,n]
	}
	//手动设定10个最大的数
	a[2] = n + 3;
	a[122] = n + 5;
	a[1233] = n + 1;
	a[12333] = n + 2;
	a[1322] = n + 8;
	a[2312] = n + 6;
	a[54612] = n + 7;
	a[546612] = n + 9;
	a[5612] = n + 10;
	a[46612] = n + 4;
	PrintTopK(a, n, 10);
}
int main()
{
	testTopK();
	return 0;
}

【数据结构】堆的实现,堆排序以及TOP-K问题,数据结构,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-650380.html

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

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

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

相关文章

  • 【数据结构】—堆排序以及TOP-K问题究极详解(含C语言实现)

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

    2024年02月08日
    浏览(47)
  • Java 数据结构篇-实现堆的核心方法与堆的应用(实现 TOP-K 问题:最小 k 个数)

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

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

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

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

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

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

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

    2024年02月07日
    浏览(51)
  • 堆的实现,画图和代码分析建堆,堆排序,时间复杂度以及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)
  • 【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法

       💯 博客内容:【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法 😀 作  者:陈大大陈 🚀 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有

    2024年02月06日
    浏览(47)
  • 【数据结构】堆的实现(向下调整和向上调整法)和堆排序的实现

    目录 一、堆的概念引入 二、小堆的实现 ①、堆的初始化--HeapInit ②、小堆的向下调整法的实现 ③、堆排序的实现  ④、堆的插入和向上调整法  ⑤、删除堆顶数据 ⑥、获取堆顶 三、时间复杂度总结: 注:本文logN表示以2为底N的对数 普通的二叉树不适合用数组来存储的,因

    2024年02月03日
    浏览(38)
  • 二叉树的顺序结构以及堆的实现——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 上篇文章,我们认识了什么是树以及二叉树的基本内容、表示方法……接下来我们继续来深入二叉树,感受其中的魅力。 目录  二叉树的顺序结构 堆的概念及结构 堆的实现   堆的创建  堆的初始化与释放空间  堆的插入 堆的删除  堆实

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

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

    2023年04月21日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包