1. Toy模板网首页
  2. > Toy博客

数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）

5月前 作者：.自定义. 分类：Toy博客 阅读(59) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划

做人要谦虚，多听听别人的意见，然后记录下来，看看谁对你有意见

一、二叉树的顺序（堆）结构及实现

1.二叉树的顺序结构

2.堆的概念及结构

3.堆的实现

3.1 向下调整算法 AdJustDown

3.2 向上调整算法 AdJustUP

3.3 堆的创建

3.3.1 向上建堆
3.3.2 向下建堆
3.3.3 堆的初始化与销毁
3.3.4 堆的插入（压栈）
3.3.5 取堆顶的数据
3.3.6 堆的删除
3.3.7 堆的数据个数
3.3.8 堆的判空

二、堆的完整实现代码

三、完结撒❀

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

一、二叉树的顺序（堆）结构及实现

1.二叉树的顺序结构

堆
物理结构：数组
逻辑结构：二叉树

顺序结构存储就是使用数组来存储，普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树更适合使用顺序结构存储。

可能有些同学不太清楚普通二叉树使用数组来存储为什么会造成空间上的浪费，这里给大家讲解一下：
我们使用数组进行二叉树的存储时，父子节点之间需要满足的关系为：

parent = (child+1)/2;
leftchild = parent2-1;
rightchild = parent2+2;
ps:parent指父节点在数组中的下标位置，leftchild指左子节点在数组中的下标位置，rightchild指右子节点在数组中的下标位置

那么对于满二叉树和完全二叉树，我们按照一层一层（层序）往数组中进行存储。
举例如下图所示，大家可以按照下图简单计算验证一下父子之间是否满足父子关系：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划

可以知道，对于满二叉树和完全二叉树进行层序存储在数组中，按照下标计算都是满足上面所述的父子关系。

而对于普通二叉树（非满二叉树，非完全二叉树），我们依然按照上面存储进行计算
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
可以发现不符合父子节点之间的关系，问题在于2节点的右节点为空，而在存储时对于空节点我们并没有在数组中进行存储记录，相当于在数组中少了一个位置，那么我们如果把空节点加上，如下图：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
这样就满足了父子间的关系，但是对于下标为4的位置并没有存储数据，就造成了空间浪费。

所以，对于普通二叉树我们一般使用链式结构进行存储，避免空间浪费。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.堆的概念及结构

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

堆的性质：

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

数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
堆的兄弟节点（同一父节点的子两个子节点）之间是不论大小的，而对于小堆其父节点的值一定小于子节点，对于大堆其父节点的值一定大于子节点。

3.堆的实现

堆初始化结构：

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

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

在给定一个数组去实现成堆之前我们需要先了解内部实现的核心逻辑。

3.1 向下调整算法 AdJustDown

现在我们给出一个数组，逻辑上看做一颗完全二叉树。

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

我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
上面数组逻辑上的二叉树可画为：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
可以看出来，根节点27影响了整体的小堆结构，那么我们如何将其转变为小堆呢？
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划

（制作不是很好大家将就着看看就行）
按照上面图片显示的流程，我们在逻辑上就把之前的二叉树变成了小堆排序，而其逻辑实现思想就是向下调整。

向下调整：

再强调一边：
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

从根开始，比较其子节点的大小，如果为大堆排序就将父节点与子节点中较大的节点交换，如果为小堆就将父节点与子节点中较小的节点交换。交换完毕继续重复以上逻辑，直到父节点大于子节点（大堆）或是父节点小于子节点（小堆）即可完成堆排序。

代码实现：

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
	//从左孩子开始,child为小孩子那个
	 int child = parent * 2 + 1;

	 while (child<n)
	 {
		 
		 if (child + 1 < n && a[child] > a[child + 1])
		 {
			++child;
		 }

		 if (a[child] < a[parent])//小堆<,大堆>
		 {
			 Swap(&a[parent], &a[child]);
			 parent = child;
			 child = child * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
}

3.2 向上调整算法 AdJustUP

在一个二叉树的数组中如果我们尾插了一个数据，可能就导致结构不再是堆。

所以我们如果是在现有的一个堆里进行数据尾插存储，那么我们要保证数据插入后还是堆，这时一般使用向上调整算法。

下面我们给出一个数组，请画出其逻辑结构二叉树：

int arr[] = {10,15,56,25,30,70}

二叉树：

数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
如果我将5尾插在数组当中，那么就相当于是将56节点的右孩子连了一个5节点：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
这显然已经不是小堆了，调整逻辑如下：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
这就是向上调整的整体逻辑：

如果是进行小堆排序，将尾节点值与其父节点的值进行比较，如果小于父节点就交换，如果进行大堆，那就判断子节点是否大于父节点，若是大于就交换。

代码实现：

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

//向上调整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;

	//while (1)严格来说不行
	while(child>0)
	{
		if (a[child] < a[parent])//小堆<,大堆>
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整算法和向上调整算法的时间复杂度都为O（logN），大家感兴趣可以算一下。

3.3 堆的创建

向上调整和向下调整都是基于已经形成了堆上面，那么如果随便给一个本就不是堆的数组，我们该如何进行建堆呢？

3.3.1 向上建堆

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个小堆，现在我们通过算法，把它构建成一个小堆。

int a[] = {5，3，6，8，2，1};

根节点左右子树不是小堆，我们怎么调整呢？

这里我们从根的左孩子节点开始向上调整，根据数组存储顺序向后以此执行，直到最后一个节点为止。

其二叉树为：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
调整逻辑：
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
从根节点的子节点开始，进行向上调整，一次调整完毕将子节点对应数组下标加1进入下一个节点进行向上调整，直到除了根的所有节点都调整完毕，二叉树便变成了堆。

代码实现：

//向上调整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;

	//while (1)严格来说不行
	while(child>0)
	{
		if (a[child] < a[parent])//小堆<,大堆>
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;

	//向上建堆 O(N*logN)
	for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
}
3.3.2 向下建堆

向下建堆就是根据向下调整的逻辑进行。

我们把二叉树分为其根和子树，再把子树分为其根和子树，将每一个分好的子树都进行向下调整，直到叶子节点为止。

我们还拿上面数组为例：

int a[] = {5，3，6，8，2，1};

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成小堆。

调整逻辑：数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划
代码实现：

//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
	//从左孩子开始,child为小孩子那个
	 int child = parent * 2 + 1;

	 while (child<n)
	 {
		 
		 //假设法选出左右节点中大/小的节点
		 if (child + 1 < n && a[child] > a[child + 1])
		 {
			++child;
		 }

		 if (a[child] < a[parent])//小堆<,大堆>
		 {
			 Swap(&a[parent], &a[child]);
			 parent = child;
			 child = child * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
}

//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
		//向下建堆 O(N)
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(php->a, php->size, i);
	}
}

向上建堆和向下建堆的时间复杂度分别为O（N*logN），O（N）。
因为向下建堆的时间复杂度小，所以我们在实际工作中进行建堆一般是选择向下建堆。

3.3.3 堆的初始化与销毁

在数据结构中，创建任何结构，都需要对其进行初始化和销毁。

代码实现：

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

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

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

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
3.3.4 堆的插入（压栈）

插入一个数到数组的尾上，再进行向上调整算法，直到满足堆。
代码实现：

//向上调整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;

	//while (1)严格来说不行
	while(child>0)
	{
		if (a[child] < a[parent])//小堆<,大堆>
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//压栈 O(logN)
void HPPush(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, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	//数据尾插向上调整
	AdJustUP(php->a, php->size-1);
}
3.3.5 取堆顶的数据

在建好的堆中返回其根部数据。
代码实现：

//返回根数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size);

	return php->a[0];
}
3.3.6 堆的删除

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

代码实现：

//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
	//从左孩子开始,child为小孩子那个
	 int child = parent * 2 + 1;

	 while (child<n)
	 {
		 
		 if (child + 1 < n && a[child] > a[child + 1])
		 {
			++child;
		 }

		 if (a[child] < a[parent])//小堆<,大堆>
		 {
			 Swap(&a[parent], &a[child]);
			 parent = child;
			 child = child * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
}

//删除根数据O(logN)
void HPPop(HP* php)
{
	assert(php);
	assert(php->size);

	//将根数据与最后一个子叶交换，再删除最后一个数据
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;

	//向下调整
	AdJustDown(php->a, php->size, 0);
}
3.3.7 堆的数据个数

代码实现：

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}
3.3.8 堆的判空

代码实现：

//判断堆是否为空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

二、堆的完整实现代码

Heap.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

typedef int HPDataType;

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

//小堆

//堆初始化
void HPInit(HP* php);
//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n);

//堆销毁
void HPDestory(HP* php);

//压栈
void HPPush(HP* php, HPDataType x);

//返回根数据
HPDataType HPTop(HP* php);

//删除根数据
void HPPop(HP* php);

//堆的数据个数
int HPSize(HP* php);

//判断堆是否为空
bool HPEmpty(HP* php);

Heap.c:

#include "Heap.h"

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

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

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

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

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

//向上调整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;

	//while (1)严格来说不行
	while(child>0)
	{
		if (a[child] < a[parent])//小堆<,大堆>
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//压栈 O(logN)
void HPPush(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, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	//数据尾插向上调整
	AdJustUP(php->a, php->size-1);
}

//返回根数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size);

	return php->a[0];
}

//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
	//从左孩子开始,child为小孩子那个
	int child = parent * 2 + 1;

	while (child < n)
	{

		if (child + 1 < n && a[child] > a[child + 1])
		{
			++child;
		}

		if (a[child] < a[parent])//小堆<,大堆>
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//删除根数据O(logN)
void HPPop(HP* php)
{
	assert(php);
	assert(php->size);

	//将根数据与最后一个子叶交换，再删除最后一个数据
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;

	//向下调整
	AdJustDown(php->a, php->size, 0);
}

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

//判断堆是否为空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;

	//向上建堆 O(N*logN)
	/*for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}*/

	//向下建堆 O(N)
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(php->a, php->size, i);
	}
}

//建堆排序

//排序
// 升序
//小堆时间复杂度太大O(N^2),用大堆进行排序O(N*logN)
//大堆

//升序  大堆 O(N*logN)
//降序  小堆 O(N*logN)
void HeapSort(HPDataType* a, int n)
{
	//根据数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdJustDown(a, n, i);
	}

	//交换根和尾的位置，删除尾，再向上调整 O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdJustDown(a, end, 0);
		--end;
	}
}

三、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下，以后还会分享更多编程知识，我们一起进步。
最后我想讲的是，据说点赞的都能找到漂亮女朋友❤
数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）,数据结构,算法,经验分享,笔记,leetcode,链表,动态规划文章来源地址https://www.toymoban.com/news/detail-854123.html

到了这里，关于数据结构进阶篇 之 【二叉树顺序存储（堆）】的整体实现讲解（赋完整实现代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构进阶篇 之 【二叉树链序存储】的整体实现讲解

    数据结构进阶篇 之 【二叉树链序存储】的整体实现讲解

    封建迷信我嗤之以鼻，财神殿前我长跪不起 1.1 手动创建 1.2 前序递归创建 2.1 前序，中序以及后序遍历概念 2.2 层序遍历概念 2.3 前序打印实现 2.4 中序打印实现 2.4 后序打印实现 2.5 层序打印实现 2.6 判断是否为完全二叉树 3.1 二叉树节点个数 3.2 二叉树第k层节点个数 3.3 二叉树

    2024年04月13日
    浏览(31)
  • 【数据结构】二叉树——顺序结构

    【数据结构】二叉树——顺序结构

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

    2024年02月02日
    浏览(37)
  • 数据结构-二叉树·堆（顺序结构的实现）

    数据结构-二叉树·堆（顺序结构的实现）

    🎉个人名片： 🐼作者简介：一名乐于分享在学习道路上收获的大二在校生 🐻‍❄个人主页🎉：GOTXX 🐼个人WeChat ： ILXOXVJE 🐼本文由GOTXX原创，首发CSDN🎉🎉🎉 🕊系列专栏：零基础学习C语言----- 数据结构的学习之路 🐓每日一句：如果没有特别幸运，那就请特别努力！🎉

    2024年02月05日
    浏览(36)
  • 数据结构：二叉树的顺序结构--堆

    数据结构：二叉树的顺序结构--堆

    朋友们、伙计们，我们又见面了，本期来给大家解读一下二叉树--堆的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！ C 语 言 专 栏：C语言：从入门到精通 数据结构专栏：数据结构 个  人  主  页 ：stackY、 目录 前言： 1.堆的概念及

    2024年02月06日
    浏览(33)
  • 【数据结构】二叉树的顺序结构-堆

    【数据结构】二叉树的顺序结构-堆

    普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而 完全二叉树 更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个

    2024年02月09日
    浏览(38)
  • 数据结构——顺序二叉树——堆

    数据结构——顺序二叉树——堆

            在介绍二叉树之前，我们首先要明确树是什么。         树 用我们的通常认识来判断应该是一种植物，从根向上生长，分出许多的树枝并长出叶子。对于数据结构中的树而言，其结构也正是从树的特征中剥离出来的。树结构是一种非线性数据结构，具有一个根结

    2024年01月19日
    浏览(33)
  • 【数据结构】二叉树的顺序结构及实现

    【数据结构】二叉树的顺序结构及实现

    目录 1. 二叉树的顺序结构 2. 堆的概念及结构 3. 堆的实现 3.1 堆向下调整算法 3.2 堆的创建 3.3 建堆时间复杂度 3.4 堆的插入 3.5 堆的删除 3.6 堆的代码实现 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉

    2024年02月08日
    浏览(31)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构，但这些数据结构都是线性的（一对一）。接下来要学习 非线性的数据结构——树（二叉树） ，相比前面的，树的结构更加复杂，话不多说，直接进入正题吧。 树是一种 非线性的数据结构 ，它是 一对多（也有可能是

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

    数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 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日
    浏览(33)
  • 初阶数据结构之---二叉树的顺序结构-堆

    初阶数据结构之---二叉树的顺序结构-堆

    今天要讲的堆，不是操作系统虚拟进程地址空间中（malloc，realloc等开空间的位置）的那个堆，而是数据结构中的堆，它们虽然名字相同，却是截然不同的两个概念。堆的底层其实是 完全二叉树 ，如果你问我，完全二叉树是什么。好吧，那我先从树开始讲起，开始我们今天的

    2024年03月14日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包