数据结构:树和二叉树概念_堆篇

图均为博主手绘 , 代码基于vs2022实现

系列文章目录

数据结构:时间复杂度
数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题
数据结构:栈篇
数据结构:队列篇
栈和队列特别篇:栈和队列的经典算法问题

前言

在计算机科学的浩瀚宇宙中，数据结构如同星辰般支撑着算法的运行。其中，堆（Heap） 这颗独特的“星辰”以其精巧的结构和高效的特性，成为了解决优先级问题、优化排序算法的核心工具。无论是操作系统中的任务调度、网络路由中的流量管理，还是日常开发中的高性能队列，堆的身影无处不在。

然而，堆的魅力不仅在于其广泛的应用，更在于它完美结合了两种经典思想——树形结构的层次化逻辑与数组存储的空间高效性。这种“形为树，体为数组”的独特设计，使得堆既能保持二叉树的操作特性，又能享受数组随机访问的高效优势。

本文将从最基础的树结构讲起，逐步揭示堆的设计哲学与实现奥秘。通过C语言的手动实现，我们将深入探讨：

• 如何用简单的数组表示复杂的树形关系
• 通过“向上调整”与“向下调整”操作维护堆的核心性质
• 堆在排序算法与优先队列中的经典应用(篇幅有限,下篇再续)

无论您是正在夯实基础的数据结构学习者，还是希望优化算法性能的开发者，本文都将通过清晰的代码示例、渐进式的原理剖析，带您真正理解堆的本质。让我们从一行行C代码出发，亲手搭建这个既熟悉又神秘的数据结构，感受算法设计与工程实践的巧妙平衡。

一.树的概念以及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 因此，树是递归定义的。
• 如下为结构图
  PS:
• 树形结构中,子树之间不能相交,否则就不是树了
• 除了根节点外,每个节点有且仅有一个父节点
• 一颗有N个节点的树有N-1条边

1.2树的相关基础概念

让我们结合着图来看:

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林

1.3树的结构

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。这是一个天才般的想法,有效解决了表示不清楚的问题:

typedef int DataType;
struct Node
{
     struct Node* _firstChild1;   // 第一个孩子结点
     struct Node* _pNextBrother;  // 指向其下一个兄弟结点
     DataType _data;              // 结点中的数据域
};

比如这张图:

他的结构就会变成这样:

二.二叉树的概念及结构

2.1二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:

• 1. 或者为空
• 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
     
     从上图可以看出：
• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分,所以二叉树是有序树
• 对于任意的二叉树,都是由,空树,只有根节点,只有左子树,只有右子树,左右子树均存在

2.2特殊的二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
  

2.3二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n₀, 度为2的分支结点个数为n₂,则有n₀ ＝n₂ ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log₂(n+1). (ps：log₂(n+1) 是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.4二叉树的结构

我们通常一两种实现方式:

• 顺序存储(数组),接下来会讲,我们称其为堆
• 链式存储(链表),我会在二叉树的专题中对链式进行更加详细的叙述,敬请期待!

三.二叉树的顺序结构及实现

3.1二叉树的顺序结构

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

• 逻辑结构:我们想象出来的,用于对数据进行操作,以及完善数据
• 物理结构;这个则是实际存储时所显现出来的,实实在在的存在系统里的结构
  
  上图是完全二叉树的例子,如果是非完全二叉树就得空出来位置来表示相对于完全二叉树的那些节点,使得空间的浪费.

3.2堆的概念及结构

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

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树.
  我们来看看堆的结构:

typedef int HPDataType;

typedef struct Heap
{                   //动态数组
	HPDataType* a;
	int size;       //有效数据个数
	int capacity;   //空间容量
}HP;

让我们来会会老朋友,增删查改吧,接下来我都会以大根堆为例开始讲

3.3准备工作

创建对应的三个文件夹:

1.Heap.h:

用于存储顺序表的结构和增删查改函数声明,以及对应的库函数;

2.Heap.c:

用于函数的实现;

3.test.c:

用于测试和修改;
ps:2和3,均要包含头文件1,即(#include"Heap.h").

3.4堆的数据操作的实现(大根堆)

1.Heap.h:

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HPDataType;
//堆的结构体
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestroy(HP* php);
//堆的检查并扩容
void CapacityCheck(HP* php);
//堆的数据交换
void Swap(HPDataType* p1, HPDataType* p2);
//堆的向上调整
void AdjustUp(HPDataType* a, int child);
//堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//返回堆顶元素
HPDataType HeapTop(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//堆的有效个数
int HeapSize(HP* php);

别急,我们马上来实现接口

2.Heap.c:

2.1堆的初始化

void HeapInit(HP* php)
{//检查,防止传空
	assert(php);
//初始化空间
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)//常规判断是否开辟失败
	{
		perror("malloc fail\n");
		return;
	}
	php->size = 0;
	php->capacity = 4;//初始化对应数据
}

2.2堆的销毁

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

	free(php->a);//常规释放开辟空间并且置空
	php->a = NULL;
	php->capacity = php->size = 0;//清空
}

2.3内存检查并且扩容

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

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return;
		}

		php->a = tmp;
		php->capacity *= 2;

	}
}

可以说和顺序表的一模一样哈哈哈

2.4堆的数据交换(调整交换)

因为我们在后续的向上调整函数,和向下调整函数中都会用到,所有我们就单独把它写出来吧

void Swap(HPDataType* p1, HPDataType* p2)
{//普通的交换逻辑
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

2.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;//则跳出while
		}
	}
}

为什么要向上调整呢?

一、维护堆序性质的核心机制

堆的核心特征是父节点与子节点的有序关系（最大堆中父≥子，最小堆中父≤子）。当新元素插入堆时：

1. 插入位置：按照完全二叉树的性质，新元素必须放在数组末尾（即树的最底层最右侧）
2. 潜在冲突：新元素可能比其父节点更大（最大堆）或更小（最小堆），破坏堆序性质

示例：在现有最大堆 [10,8,5,2,1] 中插入元素 12
插入后数组变为 [10,8,5,2,1,12]，此时子节点12 > 父节点5，需要向上调整恢复堆序

二、时间复杂度与效率平衡

向上调整提供了最优的修复路径：

1. 操作方向：从插入点向根节点单向追溯
2. 调整次数：最多需要比较交换树的高度次（即O(log n)）
3. 对比其他方案：若重新构建整个堆，时间复杂度将升至O(n)

调整过程可视化（以插入12为例）：

初始破坏状态      第一次交换后     第二次交换后      最终状态
    10             10             12             12
   /  \           /  \           /  \           /  \
  8    5   →     8    12  →     8    10  →     8    10
 / \  /         / \  /         / \  /         / \  /
2  1 12        2 1  5         2  1  5        2  1 5

三、设计一致性的必然要求

向上调整与向下调整形成对称的操作体系：

这种对称性使得：

1. 代码可维护性：统一的操作模式降低理解成本
2. 性能可预测性：所有基础操作均保持O(log n)时间复杂度
3. 扩展灵活性：为堆排序等衍生算法奠定基础

向下调整也差不多同理

2.6堆的向下调整

//传入的是数组和插入的父节点的位置
void AdjustDown(HPDataType* a, int n, int parent)
{//通过二叉树的性质算出子节点,不熟悉性质的可以回看上面的部分
	int child = parent * 2 + 1;
	while (child < n)
	{//比较左右子节点,找出最大子节点
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
//如果子节点大于父节点
		if (a[child] > a[parent])
		{//交换,找新的子节点
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//否则跳出
		}
	}
}

2.7堆的插入

void HeapPush(HP* php, HPDataType x)
{
	assert(php);//防止传空

	CapacityCheck(php);//检查是否为空

	php->a[php->size++] = x;//插入
     //然后进行向上调整,维护堆形态
	AdjustUp(php->a, php->size - 1);//因为上面size++过了
}

2.8堆的删除

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));//判断不为空
//删去堆顶元素
	Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个叶子节点
	php->size--;//再删去,之所以这样,是防止直接删除堆顶,从而造成堆的关系错乱
//重新恢复堆的关系,将换上去的原本位于叶节点的元素,向下调整
	AdjustDown(php->a, php->size, 0);//这叫维护堆
}

2.9返回堆的堆顶元素

直接return;

HPDataType HeapTop(HP* php)
{
	assert(php);

	return php->a[0];
}

2.10堆的判空

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

2.11返回堆的有效个数

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

	return php->size;
}

2.12完整代码

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

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

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

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

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

//内存检查并且扩容
void CapacityCheck(HP* php)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return;
		}

		php->a = tmp;
		php->capacity *= 2;

	}
}

//堆的调整交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

//堆的向上调整
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;
		}
	}
}

//堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}

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

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

	CapacityCheck(php);

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

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

//堆的删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

//返回堆的堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);

	return php->a[0];
}

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

	return php->size == 0;
}

//返回堆的有效个数
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

3.test.c

我们来测试看看:

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

int main()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 35);
	HeapPush(&hp, 534);
	HeapPush(&hp, 354);
	HeapPush(&hp, 215);
	HeapPush(&hp, 56);
	HeapPush(&hp, 1);//可以通过调试看看堆的过程

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	return 0;
}

3.5堆的优缺点

一、堆的核心优势

1. 高效的最值访问

• 时间复杂度：获取最大值（最大堆）或最小值（最小堆）的时间复杂度为 O(1)
• 应用场景：实时获取极值的需求（如任务调度、实时排行榜）
• 对比其他结构：比遍历数组找最值（O(n)）快得多，比平衡二叉搜索树（O(log n)）更直接

2. 动态维护效率高

• 插入/删除：时间复杂度均为 O(log n)
• 自平衡特性：通过上浮（AdjustUp）和下沉（AdjustDown）自动维护堆序性
• 对比数组：优于无序数组的插入O(1)+查找O(n)组合

// 典型插入操作示例
void HeapPush(HP* php,HPDataType x ) {
    // ...插入后自动触发shiftUp保持堆性质
}

3. 空间效率优异

• 存储方式：使用数组存储完全二叉树
• 空间利用率：无指针开销，空间复杂度为 O(n)
• 对比树结构：比普通二叉树节省约50%空间（无需左右子节点指针）

4. 堆排序优势

• 原地排序：不需要额外空间（快速排序需要O(log n)栈空间）
• 时间复杂度：始终保证O(n log n)，无最坏情况
• 适用场景：内存敏感型设备的排序需求
• 我会在下一篇博客中来深入探讨

二、堆的主要局限性

1. 查找效率低下

• 平均时间复杂度：查找任意元素需要 O(n)
• 结构限制：仅保证父子节点有序，不保证全局有序
• 对比哈希表：远慢于哈希表的O(1)查找

2. 部分操作成本高

3. 内存管理挑战

• 固定容量：数组实现需要预设容量
• 动态扩容：扩容时需要O(n)时间复制数据
• 碎片风险：频繁插入删除可能造成内存不连续

4. 应用场景局限

• 不适用的场景：
  • 需要频繁查找非极值元素
  • 需要维护完全有序的数据集
  • 需要支持范围查询（如查找10-20之间的元素）

三、与其他数据结构的对比

1. 堆 vs 有序数组

2. 堆 vs 平衡二叉搜索树（如AVL树）

3. 堆 vs 优先队列实现对比

四、实际应用中的选择建议

✅ 推荐使用堆的场景：

1. 优先队列实现：任务调度、Dijkstra算法
2. 流数据处理：实时维护Top K元素
3. 内存受限环境：嵌入式系统排序需求
4. 事件驱动模拟：离散事件的时间顺序管理

❌ 不建议使用堆的场景：

1. 数据库索引：需要支持范围查询
2. 字典应用：需要快速查找任意关键字
3. 频繁修改：需要多次修改非极值元素
4. 完全有序需求：需要按顺序遍历所有元素

总结

核心认知升华

堆的本质是矛盾统一的智慧结晶：

• 形为树，体为数组：用线性结构表达层次关系，以空间换操作效率
• 局部无序，全局有序：仅维护父子节点的大小关系，放弃全局排序
• 动静平衡：通过有限的调整（O(log n)）换取动态数据的高效管理

应用价值图谱

1. 四大核心领域

   • 📊 流式数据Top K维护（如实时热搜榜）
   • ⏱ 优先队列实现（如医院急诊分诊系统）
   • 🔧 堆排序（内存敏感场景的最后防线）
   • 🗺 图算法加速器（Dijkstra最短路径的核心引擎）

2. 独特优势场景

   • 当80%的操作集中在20%的极值元素时
   • 当内存空间比CPU时间更珍贵时
   • 当数据持续动态到达且需要即时响应时

开发者启示录

1. 优势思维

   • 学会接受"足够好"：不追求完美排序，只要关键元素触手可及
   • 拥抱局部有序：多数场景不需要全局排序的高成本
   • 预分配的艺术：空间换时间的经典实践

2. 避坑指南

   • ❌ 不要用堆实现字典功能
   • ❌ 避免频繁修改非极值元素
   • ❌ 警惕固定数组的溢出风险

3. 进阶方向

   • 探索斐波那契堆优化图算法
   • 研究d-ary堆调节树的高度与宽度平衡
   • 实践堆内存管理优化技巧（内存池/紧凑存储）

终极思考

堆的存在启示我们：在计算机科学中，绝对的完美往往不如精准的适用。它放弃全局有序的执念，选择在动态混沌中守护最关键的有序性——这种带有实用主义色彩的设计哲学，恰恰是工程思维的精华所在。

当我们凝视堆的结构，看到的不仅是一个高效的数据容器，更是人类智慧的隐喻：在复杂世界中找到核心矛盾，用有限资源维护最关键的秩序。这种在效率与功能、空间与时间、全局与局部之间游刃有余的平衡能力，正是每一位开发者需要修炼的工程艺术。

愿你编写的每一个堆：

• 在内存的方寸之间，筑起高效的秩序之城
• 于数据的洪流之中，捕捉价值的闪耀瞬间