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

系列文章目录

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

开源网站分享

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

一、树

（1）树的定义

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

（2）树的有关定义

（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) / 2
    for (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