数据结构之堆

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

目录

前言

堆的概念与结构

堆的实现

 堆的初始化

堆的销毁

堆的显示

堆的插入

堆的向上调整算法

堆的删除

堆的向下调整算法

堆的判空

获取堆顶元素

 堆的数据个数

堆的创建


前言

二叉树的顺序结构存储即使用数组存储,而数组存储适用于完全二叉树完全二叉树不会存在空间上的浪费二叉树的顺序存储在物理上是一个数组,在逻辑上是一颗二叉树

数据结构之堆,数据结构,算法

完全二叉树的顺序存储可以根据下标寻找孩子结点或者父结点,规律如下

leftchild=2*parent+1,   rightchild=2*parent+2;

parent=(child-1)/2 ;

堆的概念与结构

堆的定义:

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

数据结构之堆,数据结构,算法

  • 大根堆示意图

数据结构之堆,数据结构,算法

堆的实现

 堆总是一棵完全二叉树,堆是用数组存储的;

//堆结构的定义
//由于是顺序存储,采用顺序表定义
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* nums;//数组
	int size;//数据个数
	int capacity;//记录数组容量
}Heap;

 堆的初始化

//堆的初始化
void HeapInit(Heap* php)
{
	assert(php != NULL);
	php->nums = (HeapDataType*)malloc(sizeof(HeapDataType)*4);
	if (php->nums == NULL)
	{
		perror("malloc failed:");
		exit(-1);
	}
	php->size = 0;
	php->capacity = 4;
}

堆的销毁

void HeapDestroy(Heap* php)
{
	assert(php != NULL);

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

堆的显示

//堆的显示
void HeapPrint(Heap* php)
{
	assert(php != NULL);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->nums[i]);
	}
	printf("\n");
}

堆的插入

堆的插入是在堆尾的下一个位置插入数据并保证数组的逻辑结构为堆;

  • case 1:

当在数组尾元素的下一个位置插入的数据其值大于等于父节点的值时,仍然为小堆;

数据结构之堆,数据结构,算法

  • case 2:

当在数组尾元素的下一个位置插入的数据其值小于父节点的值时,堆的逻辑结构被破坏,采用向上调整算法,将其调整为堆;

堆的向上调整算法

堆向上调整算法的前提是当插入第k(k>1)数据,前k-1个数据为堆;

数据结构之堆,数据结构,算法

由于堆的逻辑结构为小堆,孩子结点处插入的数值小于其父节点处的值,堆的逻辑结构被破坏;首先交换child位置处与parent位置处的值,然后child=parent,parent=(child-1)/2,继续比较孩子节点与父亲结点处的数值,若不满足小堆,继续向上调整,直至根结点的位置为止或出现满足小堆的数值出现停止;

case 1:

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法

case 2:

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法

向上调整算法的时间复杂度

当插入的数据不需要调整,时间复杂度为O(1);

当插入的数据一直调整到根结点处,调整了高度h次,设满二叉树的结点个数为N,则h=log2(N+1),那么其时间复杂度为O(logn);

综上所述,时间复杂度为O(logn);

//交换
void swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//堆的向上调整算法
void AdjustUp(HeapDataType* nums, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (nums[child] < nums[parent])
		{
			swap(&nums[child], &nums[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的插入
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php != NULL);
	//检查数组容量,容量满时扩容;
	if (php->size == php->capacity)
	{
		HeapDataType* tmp = (HeapDataType*)realloc(php->nums, sizeof(HeapDataType)* 2 * (php->capacity));
		if (tmp == NULL)
		{
			perror("realloc failed:");
			exit(-1);
		}
		php->nums = tmp;
		php->capacity = 2 * (php->capacity);
	}
	//插入堆的叶结点即二叉树的叶节点
	php->nums[php->size] = x;
	php->size++;
	//任意数据插入之后还是堆吗?
	//结论是否定的-->向上调整算法-->调整为堆
	//参数设计为指向数组首元素的指针与数组尾元素的下标,返回值为空
	AdjustUp(php->nums, php->size - 1);
}

堆的删除

堆的删除是删除堆顶数据,并且保证其逻辑结构仍然为堆,删除的方法是将堆顶的数据与最后一个数据交换,然后删除数组最后一个数据,最后进行向下调整算法,保证其逻辑结构为堆;

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法

堆的向下调整算法

堆向下调整算法的前提左右子树皆为大堆或者左右子树皆为小堆;

首先利用假设法寻找同一高度处值最小的孩子,根据其左右子树为小堆还是大堆,按照小堆或大堆的原则将其交换,若为小堆,父节点处的数值大于孩子结点出的数值,则交换彼此位置;若为大堆,父节点处的数值小于孩子结点出的数值,则交换彼此位置;直至叶节点为止或出现满足其逻辑上大小堆的数值为止;

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法

堆向下调整算法的时间复杂度为O(logN);

//堆的向下调整算法
void AdjustDown(HeapDataType* nums, int n, int parent)
{
	//假设法求同一深度左右孩子最小的一个,假设左孩子为最小
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child+1 < n && nums[child] > nums[child + 1])
		{
			child++;
		}
		//无论左右孩子,child为最小,调整为小堆;
		if (nums[child] < nums[parent])
		{
			swap(&nums[child], &nums[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//堆的删除
void HeapPop(Heap* php)
{
	//删除数组首元素,并且保证逻辑为堆;
	assert(php != NULL);
	assert(php->size > 0);

	swap(&php->nums[0],&php->nums[php->size - 1]);
	php->size--;

	//向下调整
	AdjustDown(php->nums, php->size, 0);
}

堆的判空

//堆的判空
bool HeapEmpty(Heap* php)
{
	assert(php);

	return php->size == 0;
}

获取堆顶元素

//取堆顶元素
HeapDataType HeapTop(Heap* php)
{
	assert(php != NULL);
	assert(php->size > 0);

	return php->nums[0];
}

堆的数据个数

//堆的数据个数
int HeapSize(Heap* php)
{
	assert(php != NULL);
	
	return php->size;
}

堆的创建

  • 建堆方案一(向上调整建堆)

给定一个数组,这个数组逻辑上是一颗完全二叉树,而且不一定为堆,通过向上调整算法将其构建为堆;建堆的思想为以数组首元素的下一个位置为起点,利用向上调整算法,依次插入元素建堆

 向上建堆示意图(大堆)

数据结构之堆,数据结构,算法

注:向上调整建堆的时间复杂度为O(N*logN);

void HeapCreate(Heap* php, HeapDataType* nums, int n)
{
	assert(php != NULL);
	php->nums = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (php->nums == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	php->size = php->capacity = n;
	memcpy(php->nums, nums, sizeof(HeapDataType)*n);
	//向上调整建堆,建堆的时间复杂度为O(N*logN);
	for (int i = 1; i<n; i++)
	{
		AdjustUp(php->nums,i);
	}
}
  • 建堆方案二(向下调整建堆)

当数据无序存放于数组,数组逻辑上是一颗完全二叉树,而且不一定为堆,以倒数第一个非叶子结点为起点向下建堆,由于对于倒数第一个叶子结点其左右子树只有一个数据,既可以看作大堆,也可以看作小堆向下建堆的前提为其左右子树皆为大堆或者皆为小堆,如此可自底向上调整为堆;

向下建堆示意图(大堆)

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法 数据结构之堆,数据结构,算法

 上图倒数第一个非叶子结点parent=(child-1)/2; 而child为数组尾元素的下标;上图直至调整到根节点为止;

向下调整建堆的时间复杂度为O(N);

void HeapCreate(Heap* php, HeapDataType* nums, int n)
{
	assert(php != NULL);
	php->nums = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (php->nums == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	php->size = php->capacity = n;
	memcpy(php->nums, nums, sizeof(HeapDataType)*n);
	//向下调整建堆,建堆的时间复杂度为O(N);
	for (int i = (n-1-1)/2; i>=0; i--)
	{
		AdjustDown(php->nums, n,i);
	}
}

Top-K问题

Top-K问题:求取一组数据中前K个最大的元素或者最小的元素
1. 数据集合前K个元素建堆
前K个最大的元素,则建小堆;
前K个最小的元素,则建大堆;

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

假设数组中含有50个数据,取这50个数据中最大的三个

首先前3个元素建堆---->建小堆

数据结构之堆,数据结构,算法

数据结构之堆,数据结构,算法 

由于是小堆,根节点处的数值最小(X<Y&&X<Z),当M大于X时,替换X,并且向下调整为小堆,如此当下一次插入数值,循环往复,挑选出前K个最大的数据;文章来源地址https://www.toymoban.com/news/detail-725980.html

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

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

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

相关文章

  • 【数据结构之堆的实现】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续学习怎么实现基本的操作。所以先建议看完上篇知识点,才有助于消化知识和理解。 / 知识点汇总 / 概念 :堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看

    2024年01月19日
    浏览(43)
  • 数据结构之堆的应用

    在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。 对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。 目录 1.top k问题(优质筛选问题) 2.堆排序 1.向

    2024年02月08日
    浏览(52)
  • 【数据结构--八大排序】之堆排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 口诀:排降序,建小

    2024年02月08日
    浏览(46)
  • 数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 1.1.堆的概念 1.2.堆的存储结构 二.堆的功能实现 2.1.堆的定义 2.2.堆的初始化 2.3.堆的销毁 2.4.堆的打印 2.5.堆的插入 向上调整算法 堆的插入 2.6.堆的删除 向下调整算法 堆的删除 2.7.堆的取堆顶元素 2.8.堆的判空 2.9.堆的求堆的大小 三.堆的创建 3.1.向上调

    2024年02月14日
    浏览(45)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(82)
  • 数据结构之堆的实现(图解➕源代码)

            首先明确堆是一种特殊的完全二叉树,分为大根堆和小根堆,接下来我们就分别介绍一下这两种不同的堆。         在大堆里面: 父节点的值  ≥  孩子节点的值          我们的兄弟节点没有限制,只要保证 每个父节点都≥孩子节点 就行。         在小堆

    2024年02月06日
    浏览(47)
  • 数据结构学习分享之堆的详解以及TopK问题

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 本章就给大家带来久违的堆的知识,如果你还不知道数的相关知识,或者什么是完全二叉树,请跳转 树的介绍, 本章的堆结

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

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

    2024年02月05日
    浏览(43)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(53)
  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中,算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究,展示了算法在项目管理中的实际应用: 项目进度管理 : 甘特图算法 :甘特图是一种项目进度管理工具,它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包