完全二叉树的顺序存储【堆】

系列文章目录

🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
😍 👋🏼🎉🎊创作不易，欢迎大家留言、点赞加收藏！！！ 🥳😁😍

---

开源网站分享

在开始总结之前，给各位分享一个开源网站：
开源各种常见算法的可视化展示

一、树

（1）树的定义

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

（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）棵互不相交的树的集合称为森林；

（3）树的有关结论

1. 在树中，所有的节点的度数之和 = 所有的节点总数 - 1；
2. 任何一棵树，都可以看作：根和子树；
3. 一颗N个节点的树 有N-1条边；

二、二叉树

（1）二叉树的定义

一棵二叉树是结点的一个有限集合，
该集合:
（1） 或者为空
（2） 由一个根节点加上两棵分别称为 左子树和右子树 的二叉树组成。
（3）二叉树 度的范围是【0,2】。

注意：
对于任意的二叉树都是由以下几种情况复合而成的：

（2）特殊的两种二叉树

满二叉树

一种二叉树，每一个层的结点数都达到最大值；

完全二叉树

一种二叉树，
要求：
（1）前 h-1 层的结点数都达到最大值。
（2）最后一层没有达到最大值，但要求从左到右是连续的；

（3）二叉树的有关结论

补充：

完全二叉树 度为1的节点总数 为 0 或 1。

三、堆(一种二叉树)

（1）堆的定义

（2）堆的有关结论

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

（3）堆的创建

向上调整算法（AdjustUp）

以建大堆为例，如果该节点的数值大于双亲节点的数值，则进行交换数值，以此类推，直到最后一个节点。

注意事项：

向上调整算法 的使用前提是：进行调整算法之前，原来的数组满足堆的定义。

代码示例

// 向上调整算法，用于在堆中从下往上调整元素，使其满足堆的性质
void AdjustUp(HPDataType* a, int child)
{// 找到双亲节点的下标，通过公式 (child - 1) / 2 计算得到int parent = (child - 1) / 2;// 孩子节点的下标不是 0（根节点的下标），即不是根节点时，进行循环调整while (child > 0){// 如果孩子节点的数值大于双亲节点的数值，说明不满足堆的性质，需要调整if (a[child] > a[parent]){// 交换孩子节点和双亲节点的数值，使较大的数值上移Swap(&a[child], &a[parent]);// 更新孩子节点和双亲节点的下标，继续向上调整child = parent;parent = (child - 1) / 2;}else{// 如果孩子节点的数值不大于双亲节点的数值，说明已经满足堆的性质，退出循环break;}}
}

向下调整算法（AdjustDown）

以建大堆为例，从倒数的第一个叶子节点（n-1）的双亲节点（n-1-1）/2，如果孩子节点的数值大于双亲节点的数值，则进行交换数值，以此类推，直到根节点。

代码示例

// 向下调整算法，用于堆的调整操作，使以 parent 为根的子树满足堆的性质
void AdjustDown(HPDataType* a, int n, int parent)
{// 计算 parent 节点的左孩子的索引int child = parent * 2 + 1;// 当左孩子索引小于数组长度时，继续循环，即 parent 节点有孩子时while (child < n){// 选出左右孩子的较大者，如果右孩子存在且右孩子大于左孩子，则将 child 指向右孩子if ((child+1 < n)&&(a[child+1]>a[child])){++child;}// 如果较大孩子大于 parent 节点，则交换它们的值if (a[child] > a[parent]){Swap(&a[child], &a[parent]);// 更新 parent 和 child 的索引，继续向下调整parent = child;child = parent * 2 + 1;}// 如果 parent 节点已经大于其孩子，则无需继续调整，退出循环else{break;}}
}

注意事项：

向下调整算法 的使用前提是：进行调整算法之前，除去根节点，剩下的两颗子树满足堆的定义。

四、堆排序

（1）堆排序的定义

堆排序（Heapsort）是一种利用堆数据结构实现的排序算法‌。
堆是一种近似完全二叉树的结构，分为大堆和小堆。
在最大堆中，父节点的值总是大于或等于其子节点的值；
而在最小堆中，父节点的值总是小于或等于其子节点的值。‌

（2）堆排序的具体实现

（1） 构造“大堆”(小堆)，根节点为最值 ；
（2）将最值与待排序序列的最后一个元素交换， 继续对其构造“大堆”(小堆)，待排序序列元素个数减一，直至只剩一个元素。

（3）源码示例

注意事项：

这个示例是 建大堆，将数据升序。

方法1

先使用向上调整算法（AdjustDown）建大堆，然后再进行升序排列。

// 堆排序函数，对数组 a 中的 n 个元素进行排序
void HeapSort(int* a, int n)
{// 向上调整算法 -- 建大堆// 从第二个元素开始（索引为 1）// 通过向上调整，将每个元素放到合适的位置，使得整个数组满足大堆的性质for (int i = 1; i < n; ++i){AdjustUp(a, i);}// 升序排列// 初始化 end 为最后一个元素的索引int end = n - 1;// 当 end 大于 0 时，即还有元素未排序时，继续循环while (end > 0){// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换Swap(&a[end], &a[0]);// 对未排序部分的堆进行向下调整，重新调整为大堆// 此时未排序部分的元素个数为 end，从根节点（索引为 0）开始调整AdjustDown(a, end, 0);// 未排序部分的元素个数减 1--end;}
}

方法2

先使用向下调整算法（AdjustDown）建大堆，然后再进行升序排列。

// 堆排序函数，对数组 a 中的 n 个元素进行排序
void HeapSort(int* a, int n)
{// 向下调整算法 -- 建大堆// 从最后一个非叶子节点开始向下调整// n 是数组的个数，节点的索引需要减 1// 最后一个非叶子节点的索引为 (n - 1 - 1) / 2for (int i = (n - 1 - 1) / 2; i >= 0; --i){// 对每个非叶子节点进行向下调整，使得以该节点为根的子树满足大堆的性质AdjustDown(a, n, i);}// 升序排列// 初始化 end 为最后一个元素的索引int end = n - 1;// 当 end 大于 0 时，即还有元素未排序时，继续循环while (end > 0){// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换Swap(&a[end], &a[0]);// 对未排序部分的堆进行向下调整，重新调整为大堆// 此时未排序部分的元素个数为 end，从根节点（索引为 0）开始调整AdjustDown(a, end, 0);// 未排序部分的元素个数减 1--end;}
}

---

END

每天都在学习的路上！
On The Way Of Learning