二叉树 - 堆 | 数据结构中的小技巧大作用

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


二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人,再渺小也不会迷途。

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

一、堆的概念及介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵完全二叉树的数组。

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段

堆满足下列性质:

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

将根节点最大的堆叫做最大堆大根堆,根节点最小的堆叫做最小堆小根堆
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法


二、结构图示

二叉堆是一颗完全二叉树,且堆中某个节点的值总是不大于其父节点的值,该完全二叉树的深度为 k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆,如下图所示:
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法
我们可以使用数组存储二叉堆,右边的标号是数组的索引。
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

假设当前元素的索引位置为 i,可以得到规律:

parent(i) = i/2(取整)
left child(i) = 2*i+1
right child(i) = 2*i +2

三、堆的代码实现(图解)

3.1 创建堆结构体即接口

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化 (可要可不要)
void HeapInit(Heap* hp);
// 堆的构建
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);

3.2 堆的初始化 && 交换两个数(用于parent 和 child 的交换 )

// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

3.3 堆的向上调整

注意:此算法的前提是 在进行向上调整前此树已经是堆
向上调整操作用于在插入新元素时保持堆的性质。

算法思想如下:

  1. 首先,计算给定节点的父节点索引。如果当前节点是根节点(即索引为0),则没有父节点,不需要进行向上调整。

  2. 然后,进入一个循环,条件是当前节点的索引大于0。这是因为根节点已经是堆中的最大值(对于大顶堆)或最小值(对于小顶堆),无需再向上调整。

  3. 在循环中,比较当前节点和其父节点的值。如果当前节点的值小于其父节点的值(对于大顶堆)或大于其父节点的值(对于小顶堆),则需要进行向上调整。

  4. 交换当前节点和其父节点的值,将父节点移动到正确的位置。然后更新当前节点的索引为父节点的索引,并重新计算父节点的索引。

  5. 如果当前节点的值大于或等于其父节点的值(对于大顶堆)或小于或等于其父节点的值(对于小顶堆),则说明已经到达了正确的位置,可以跳出循环。

通过以上步骤,可以实现向上调整操作,确保堆的性质得到维护。
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

//向上调整 --- 插入时使用,保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

时间复杂度分析
最坏的情况下是从第一个非叶子节点一路比较到根节点,比较的次数为完全二叉树的高度-1,即时间复杂度为 O(log2N)

3.4 堆向下调整算法(以小堆为例)

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提:左右子树必须是一个堆,才能调整

int array[] = {27,15,19,18,28,34,65,49,25,37};

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

算法思想如下:

  1. 假设当前节点的左孩子为最小值节点。
  2. 判断当前节点是否有右孩子,如果有且右孩子的值小于左孩子的值,则将右孩子的下标赋值给child
  3. 如果当前节点的值大于child节点的值,说明需要向下调整,交换当前节点和child节点的值。
  4. 更新parentchild,继续向下调整。
  5. 如果当前节点的值小于等于child节点的值,说明已经找到合适的位置,跳出循环。

通过以上步骤,可以实现向下调整操作,确保堆的性质得到维护。
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小,则将child的下标置为右孩子的下标
		if (child + 1 < size && a[child] > a[child + 1]) //后面的 “>” 改成 “<”即为大堆的向下调整
		{
			child++;
		}

		if (a[child] < a[parent]) // “<”改成“>”即为大堆的向下调整
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

时间复杂度分析
最坏的情况即图示的情况,从根一路比较到叶子节点,比较的次数为完全二叉树的高度,即时间复杂度为 O(log2N)

3.5 堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆

int a[] = {1,5,3,8,7,6}; 

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法
【1】向上调整建堆

//向上调整建对堆 --- 0(N*logN)
int n = sizeof(a) / sizeof(a[0]);

for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

【2】向下调整建堆

// 向下要调整建堆 --- O(N) 
int n = sizeof(a) / sizeof(a[0]);
//找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}

【3】模拟堆插入的过程建堆

// 堆的构建 --- 小堆 O(logN)
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	//模拟堆插入的过程建堆
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}
【向上调整建堆时间复杂度】

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

【向下调整建堆时间复杂度】

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

二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

3.6 堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
二叉树 - 堆 | 数据结构中的小技巧大作用,数据结构冒险记,数据结构,堆,二叉树,算法

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

	AdjustUp(hp->a, hp->size - 1);
}

3.7 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//从父亲的位置开始往下调
	AdjustDown(hp->a, hp->size, 0);
}

3.8 取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}

3.9 求堆的数据个数

// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

3.10 堆的判空

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

四、源代码

4.1 Heap.h文件

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化(可要可不要)
void HeapInit(Heap* hp);
// 堆的构建
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);

4.2 Heap.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"


// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

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

// 堆的构建 --- 小堆
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);

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

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


//向上调整 --- 插入时使用,保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 堆的插入 --- O(logN)
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

	AdjustUp(hp->a, hp->size - 1);
}

//向下调整 --- 删除的时候使用
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小,则将child的下标置为右孩子的下标
		if (child + 1 < size && a[child] > a[child + 1]) //后面的 “>” 改成 “<”
		{
			child++;
		}

		if (a[child] < a[parent]) // “<”改成“>”即为大堆的向下调整
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//从父亲的位置开始往下调
	AdjustDown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}
// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

4.3 Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void Test1()
{
	int a[] = { 4,6,2,1,5,8,2,9 };
	Heap hp;
	int len = sizeof(a) / sizeof(a[0]);
	//HeapInit(&hp);
	模拟堆插入的过程建堆
	//for (int i = 0; i < len; i++)
	//{
	//	HeapPush(&hp, a[i]);
	//}
	HeapCreate(&hp, a, len);

	//打印堆中前k个元素
	/*int k = 4;
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}*/
	//打印堆
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp)); 
		HeapPop(&hp);
	}
	printf("\n");
}

int main()
{
	Test1();
	return 0;
}

今天的分享到此结束,后续将继续向大家带来更多数据结构的小知识!文章来源地址https://www.toymoban.com/news/detail-814435.html

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

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

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

相关文章

  • 数据结构与算法学习:二叉树的后序遍历的递归与非递归实现,以及非递归实现中的流程控制的说明。

    需求二叉树: 采用二叉树后序遍历非递归算法。设置一个指针p初始指向树根,p先入栈,而后使得p指向它的左孩子p-firstchild,重复操作,使得每个左孩子都依次入栈,同时初始化一个Treenode*类型的指针 pre,这个指针是后序前驱,这个后序前驱用以区分为已访问过的结点和未

    2023年04月22日
    浏览(47)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(55)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(54)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(39)
  • 【数据结构】二叉树的介绍和二叉树堆

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        树这一概念,在我们刚开始听说的时候会觉得

    2024年01月20日
    浏览(49)
  • 数据结构之二叉树和平衡二叉树

    1、二叉树: 2、平衡二叉树:

    2024年04月17日
    浏览(44)
  • 【数据结构】 二叉树理论概念!一文了解二叉树!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! 什么是二叉树?二叉树的组成构造是什么样的?我们将由浅入深,循序渐进的方式把二叉树给搞明白,让你彻底了解二叉树! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一

    2024年02月05日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包