文章目录前言一、树的概念1.1 树的定义1.2 树的相关术语1.3 树的表示1.4 树在实际中的应用二、二叉树概念及结构2.1 二叉树的定义2.2 现实中的二叉树2.3 特殊的二叉树2.4 二叉树的性质2.5 二叉树的存储结构1. 顺序存储2. 链式存储三、堆的概念与结构3.1 堆的定义3.2 堆的存储结构四、堆的基本功能实现4.1 辅助函数向上调整和向下调整4.1.1 向上调整AdjustUp4.1.2 向下调整AdjustDown4.2 接口实现4.2.1 初始化与销毁4.2.2 插入元素4.2.3 删除堆顶元素4.2.4 其他简单接口4.2.5 建堆五、堆排序5.1 堆排序代码实现5.2 堆排序的时间复杂度结语前言在计算机科学中树是一种非常重要的非线性数据结构它以层次化的方式组织数据广泛应用于文件系统、编译原理、数据库索引等领域。而堆作为一种特殊的完全二叉树不仅实现了高效的优先队列更是堆排序算法的核心。本文将带你从树的基础概念出发逐步深入堆的实现并最终掌握堆排序的原理与代码编写。一、树的概念1.1 树的定义树Tree是由 nn≥0个有限结点组成的一个具有层次关系的集合。当 n0 时称为空树。在任意一棵非空树中有且仅有一个特定的结点称为根结点根结点没有前驱结点。除根结点外其余结点可以分成 MM0个互不相交的有限集合 T₁、T₂、...、Tₘ其中每一个集合本身又是一棵树称为根结点的子树。树的定义是递归的树由根和若干互不相交的子树构成而子树本身也是一棵树。1.2 树的相关术语结点的度一个结点拥有的子树个数。叶结点终端结点度为 0 的结点。分支结点非终端结点度不为 0 的结点。父结点与子结点若结点 A 有孩子 B则 A 是 B 的父结点B 是 A 的子结点。兄弟结点具有相同父结点的结点。树的度树中所有结点的度的最大值。结点的层次从根开始定义根为第 1 层根的子结点为第 2 层以此类推。树的高度深度树中结点的最大层次。森林由 mm≥0棵互不相交的树组成的集合。1.3 树的表示在实际编程中我们需要用某种数据结构来存储树。树有多种表示方法如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等。最常用的是孩子兄弟表示法也称为左孩子右兄弟表示法。这种表示法可以将任意一棵树转化为二叉树的形式从而方便地使用二叉树的算法进行处理。孩子兄弟表示法的结点结构如下typedef int DataType; struct Node { struct Node* firstChild; // 指向第一个孩子结点 struct Node* pNextBrother; // 指向下一个兄弟结点 DataType data; // 结点中的数据域 };1.4 树在实际中的应用树结构在计算机中应用广泛最典型的例子就是文件系统的目录树结构。根目录类似于树的根结点子目录和文件则对应分支结点和叶结点。通过树形结构我们可以高效地组织和管理文件。二、二叉树概念及结构2.1 二叉树的定义二叉树Binary Tree是每个结点最多有两个子树的树结构并且子树有左右之分次序不能颠倒。二叉树的定义也是递归的要么为空树要么由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。2.2 现实中的二叉树2.3 特殊的二叉树满二叉树如果一棵二叉树的每一层结点数都达到最大值即深度为 k 的满二叉树有 2^k - 1 个结点那么它就是满二叉树。满二叉树的特点是所有分支结点都有左右子树且叶结点都在最底层。完全二叉树对于深度为 k 的二叉树如果其结点与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应即从上到下、从左到右编号则称为完全二叉树。完全二叉树的特点是叶结点只可能出现在最后两层最后一层的叶结点都靠左排列若某个结点没有左孩子则一定没有右孩子。满二叉树是特殊的完全二叉树。2.4 二叉树的性质二叉树具有以下重要性质假设根结点层数为 1第 i 层最多结点数在二叉树的第 i 层上最多有 2^(i-1) 个结点i ≥ 1。深度为 h 的最大结点数深度为 h 的二叉树最多有 2^h - 1 个结点。叶子结点数与度为 2 的结点数的关系对任意非空二叉树若叶子结点数为 n₀度为 2 的结点数为 n₂则 n₀ n₂ 1。这一性质可以通过总边数关系推导得出总结点数 N n₀ n₁ n₂总边数 N - 1 n₁ 2n₂联立得 n₀ n₂ 1具有 n 个结点的完全二叉树深度h ⌊log₂(n)⌋ 1或 h ⌈log₂(n1)⌉。完全二叉树结点编号特性若对完全二叉树按从上到下、从左到右从 0 开始编号则对于编号为 i 的结点若 i 0其父结点编号为 (i-1)/2若 2i1 n其左孩子编号为 2i1否则无左孩子若 2i2 n其右孩子编号为 2i2否则无右孩子。2.5 二叉树的存储结构二叉树有两种常用的存储方式顺序存储和链式存储。1. 顺序存储顺序存储使用数组来存放二叉树的结点。对于完全二叉树这种存储方式非常高效因为结点在数组中的位置可以直接反映其逻辑关系利用上述编号特性。但对于非完全二叉树数组会浪费大量空间因此通常只用于完全二叉树如堆。2. 链式存储链式存储使用结点结构体每个结点包含数据域以及指向左孩子和右孩子的指针。这是最常用的二叉树存储方式结构如下typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向当前结点左孩子 struct BinaryTreeNode* right; // 指向当前结点右孩子 BTDataType data; // 当前结点值域 } BTNode;三、堆的概念与结构3.1 堆的定义如果有一个关键码的集合 K {k₀, k₁, k₂, ..., kₙ₋₁}将其所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足大堆大根堆任意结点的值都大于或等于其左右孩子结点的值即 Kᵢ ≥ K₂ᵢ₊₁ 且 Kᵢ ≥ K₂ᵢ₊₂。小堆小根堆任意结点的值都小于或等于其左右孩子结点的值即 Kᵢ ≤ K₂ᵢ₊₁ 且 Kᵢ ≤ K₂ᵢ₊₂。堆具有以下性质堆中某个结点的值总是不大于或不小于其父结点的值。堆总是一棵完全二叉树。3.2 堆的存储结构堆通常使用顺序存储即用一个一维数组来存储堆中的所有结点。由于堆是完全二叉树数组下标可以自然映射结点位置若根结点下标为 0则对于下标为 i 的结点父结点下标(i - 1) / 2左孩子下标2 * i 1右孩子下标2 * i 2四、堆的基本功能实现下面我们以小堆为例实现一个动态增长的堆。我们将提供以下接口typedef int HeapdataType; typedef struct Heap { HeapdataType* arr; int size;//这里的size指向最后一个元素的下一个位置初始化时置为0 int capacity; }Hp; void HeapInit(Hp* hp); void HeapDestroy(Hp* hp); void Swap(HeapdataType* n1, HeapdataType* n2); void AdjustUp(HeapdataType* arr,int child); void HeapPush(Hp* hp, HeapdataType x); void AdjustDown(HeapdataType* arr, int size, int parent); void HeapPop(Hp* hp); HeapdataType HeapTop(Hp* hp); int HeapSize(Hp* hp); bool HeapEmpty(Hp* hp);4.1 辅助函数向上调整和向下调整堆的核心操作是插入和删除它们依赖于两个关键调整算法向上调整和向下调整。4.1.1 向上调整AdjustUp插入数据后如果堆的结构被破坏那么就需要进行向上调整观察原堆的结构如果插入之前是小堆,那么就将小的向上调整如果插入之前是大堆那么将向上调整的代码中的改为。我们这里都是小堆.void AdjustUp(HeapdataType* arr,int child) { int parent (child - 1) / 2; while (child 0) { if (arr[parent] arr[child]) { Swap(arr[parent], arr[child]); child parent; parent (child - 1) / 2; } else { break; } } }4.1.2 向下调整AdjustDown删除堆顶元素时通常先将堆顶与最后一个元素交换然后删除最后一个元素即原堆顶再从新的堆顶开始向下调整与左右孩子中较小小堆或较大大堆的交换直到满足堆序或成为叶子。void AdjustDown(HeapdataType* arr, int size, int parent) { //因为我们要找出左右孩子中较小的那一个进行交换 //我们先假设左孩子是较小的那一个 int child 2 * parent 1; while (child size) { if (child 1 size arr[child 1] arr[child]) { child; } if (arr[child] arr[parent]) { Swap(arr[child], arr[parent]); parent child; child 2 * parent 1; } else { break; } } }4.2 接口实现4.2.1 初始化与销毁void HeapInit(Hp* hp) { assert(hp); hp-arr NULL; hp-capacity hp-size 0; } void HeapDestroy(Hp* hp) { assert(hp); free(hp-arr); hp-arr NULL; hp-size hp-capacity 0; }4.2.2 插入元素void HeapPush(Hp* hp, HeapdataType x) { assert(hp); if (hp-size hp-capacity)//如果空间满了对数组进行扩容 { int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity; HeapdataType* newarr (HeapdataType*)realloc (hp-arr, sizeof(HeapdataType) * newcapacity); if (newarr NULL) { perror(realloc failed); return; } hp-arr newarr; hp-capacity newcapacity; } hp-arr[hp-size] x; AdjustUp(hp-arr, hp-size - 1); }4.2.3 删除堆顶元素void HeapPop(Hp* hp) { assert(hp); assert(hp-size0);//确保其中至少有一个元素 //为了保证不同时改变左右子树的结构我们将第一个元素与最后一个元素交换 Swap(hp-arr[0], hp-arr[hp-size - 1]); hp-size--; //交换之后我们需要将第一个元素进行向下调整保证堆结构的完整性 AdjustDown(hp-arr, hp-size, 0); }4.2.4 其他简单接口HeapdataType HeapTop(Hp* hp) { assert(hp); assert(hp-size 0); return hp-arr[0]; } int HeapSize(Hp* hp) { assert(hp); return hp-size; } bool HeapEmpty(Hp* hp) { assert(hp); return hp-size 0; }4.2.5 建堆给定一个数组我们如何将它调整成一个堆常用的方法是向下调整建堆从最后一个非叶子结点开始依次向前对每个结点执行向下调整。最后一个非叶子结点的下标为 (n-1-1)/2 n/2 - 1。for (int i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(hp-_a, n, i); }五、堆排序堆排序是利用堆这种数据结构进行排序的一种算法其基本思想是建堆将待排序序列构建成一个堆升序建大堆降序建小堆。排序不断将堆顶元素与堆尾元素交换交换后堆的大小减一然后对新的堆顶执行向下调整重复此过程直到堆为空。以升序排序为例我们需要建大堆这样堆顶是最大值然后每次将最大值交换到最后并调整剩余元素为大堆最终得到升序序列。5.1 堆排序代码实现void HeapSort(int* a, int n) { // 1. 建堆升序建大堆 for (int i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(a, n, i); } // 2. 排序 int end n - 1; while (end 0) { Swap(a[0], a[end]); // 将堆顶最大值交换到最后 AdjustDown(a, end, 0); // 调整剩余的元素为大堆 end--; } }注意上述代码中的AdjustDown需要根据堆的类型调整比较逻辑。若用于大堆向下调整时应将父结点与较大的孩子交换。5.2 堆排序的时间复杂度建堆阶段O(n)排序阶段每次交换后向下调整的时间复杂度为 O(log n)共进行 n-1 次因此排序阶段为 O(n log n)总时间复杂度O(n log n)空间复杂度O(1)原地排序不需要额外空间结语树作为重要的非线性结构为我们提供了分层组织数据的能力。而堆作为完全二叉树的典型应用不仅实现了优先队列还衍生出高效的堆排序算法。通过本文的学习我们掌握了堆的核心操作向上调整、向下调整及其在插入、删除、建堆、排序中的具体实现。希望读者能够动手编写代码深入理解堆的精髓并在实际问题中灵活运用。