数据结构动图详解二叉树——堆及堆排序_c语言二叉树堆排序

一、树的概念

        1、树的特征

        2、树的相关名词

二、树的表示方法

        1、左孩子右兄弟表示法

        2、双亲表示法

三、特殊二叉树

四、堆的向上调整算法建堆及排序

        1、向上调整建堆O(N*logN)

        2、向上调整用于排序

五、堆的向下调整算法

        1、向下调整建堆O(N)

        2、向下调整用于排序

        3、堆排序总结

一、树的概念
1、树的特征
        树是非线性的数据结构，是递归定义的。

        子树之间不能有任何交集

        一颗N个节点的树有N-1条边

2、树的相关名词
        1、节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

        2、叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点

        3、非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点

        4、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点。

        5、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

        6、兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

        7、树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

        8、节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

        9、 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4（若定义根为第一层，空树为第零层；若定义根节点为第零层，则空树为-1层。）

        10、堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

        11、节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

        12、子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

        13、森林：由m（m>0）棵互不相交的树的集合称为森林；

二、树的表示方法
        1、左孩子右兄弟表示法
        typedef int DataType;
        struct Node
        {
         struct Node* _firstChild1; // 第一个孩子结点
         struct Node* _pNextBrother; // 指向其下一个兄弟结点
         DataType _data; // 结点中的数据域
        };
        该方法思想是让根节点找第一个孩子，让这个孩子去找他的兄弟节点

        2、双亲表示法
        在数组里存储父亲的下标

三、特殊二叉树

        1、在二叉树中，节点个数往往用于衡量时间复杂度

        2、对于任何一颗二叉树，度为0的节点总比度为2的节点多1

        3、父子节点的关系

        （左右孩子都是这个公式）

        4、满二叉树每一层都是满的，假设该颗满二叉树的高度为h，总节点为N，

        则

        5、完全二叉树前h-1层是满的，最后一层从左往右必须是连续的。

四、堆的向上调整算法建堆及排序
        堆是一个完全二叉树

        1、向上调整建堆O(N*logN)
        建堆特点：越靠近堆顶，节点个数越少，调整次数也少；越接近堆底，节点个数指数级增多，调整次数也多，所以向上调整建堆不如向下调整建堆

        void AdjustUp(HPDataType* parr, int child)//向上调整算法,建小堆
        {
            int parent = (child - 1) / 2;
            while (parr[parent] > parr[child])//这里大于变小于就是大堆
            {
                Swap(&parr[parent], &parr[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
        }
向上调整算法是在数组的末尾插入一个数，把这个数和他的父节点比较，根据建的大堆还是小堆来决定是否交换数据。如果建的是大堆，那么堆顶的那个数字是最大的。建小堆，堆顶是最小的数。

注意：建堆完成后，数组并不是有序的，只是在堆顶选出了数组中最大/最小的数。

这里是在模拟建小堆的过程，如果想用向上调整算法建大堆，在代码注释位置更换比较符号即可

        2、向上调整用于排序
        我们假设最坏情况下，每一个新的数插入进来都要向上调整，且最多调整次数为（高度-1）次，

        那么总调整次数=每一层节点个数*这一层节点最坏向上调整次数

         可得T(h)=+·······+

        1、化简得T(h)=

        2、已知高度为h，总节点个数为N的完全二叉树，——>

        在二叉树中，节点个数往往用于衡量时间复杂度

        结论：向上调整算法用于建堆的时间复杂度为O(N*logN)，建堆的时间复杂度不如向下调整算法，不采用向上调整来排序。

五、堆的向下调整算法
        1、向下调整建堆O(N)
条件：左右子树必须均为大堆/小堆，才能使用向下调整建堆

        建堆特点：越靠近堆顶，节点个数越少，调整次数多；越接近堆底，节点个数多，调整次数也少。堆排序使用向下调整。

        void AdjustDown(HPDataType* parr, int size, int parent)//向下调整算法,小堆
        {
            int minChild = parent * 2 + 1;
            while (minChild<size)
            {
                if (minChild+1<size&&parr[minChild + 1] < parr[minChild])//小堆<，大堆>
                {
                    ++minChild;//找出小的下标
                }
                if (parr[minChild] < parr[parent])//小堆<，大堆>
                {
                    Swap(&parr[minChild], &parr[parent]);
                    parent = minChild;
                    minChild = parent * 2 + 1;
                }
                else
                    break;
            }
        }

        向下调整是根据父节点向子节点向下调整，不断向下更新父节点的下标，当左孩子的下标越界时，停止向下调整。

        同样，建完堆后，数组并不是有序的，堆顶是最大/最小的数

        2、向下调整用于排序
        堆排序的原理：1、建堆2、把堆顶元素放到数组末尾3、缩小数组范围微调维持堆形态4、迭代上述步骤至有序。

        所以升序建大堆，降序建小堆

        //堆排序，实质是选择排序，依次选数，从后往前排，时间复杂度O(N*logN)
        //升序大堆
        //降序小堆
        void HeapSort(int* parr, int size)
        {
            for (int i = (size - 1 - 1) / 2; i >= 0; --i)//建堆，时间复杂度O(N)
            {//从最后一个节点的父亲开始调整,不要从size-1开始调整，因为最后一层不用调整
                AdjustDown(parr,size,i);//向下调整算法，这里用于把外部传入的数组进行建堆
            }
           for (int i = 0; i < size; ++i)//将堆顶和最后一个元素互换，再迭代向下调整选出次大/次小
            {
                Swap(&parr[0], & parr[size - 1 - i]);
                AdjustDown(parr, size - 1 - i, 0);//重建堆
            }
        }

        建堆：从最后一个节点的父亲开始向下调整，直到调整到根。（千万不要从最后一个元素开始建堆，因为叶节点的子树为空，无需向下调整。并且这些叶节点就占了整颗二叉树一半的节点）的意思：找到最后一个非叶节点

        我们假设最坏情况下，每一个非叶节点都要调整，最多调整次数为（高度-当前层数）次，

        那么总调整次数=每一层节点个数*这一层节点最坏向下调整次数

         T(h)=+·······+最后一层无需调整

        化简得T(h)=

         带入高度与节点数的关系可得时间复杂度为

        即建堆时间复杂度O(N)

        重建堆：时间复杂度O(N*logN)，粗略计算方法：最后一层节点个数为，约占总结点的一半，对于最后一层时间复杂度=该层节点数*调整次数=。其他层节点数量加起来和最后一层一样，但每个节点的调整次数少于最后一层，所以，其它层所有节点加起来的时间复杂度都不如最后一层所有节点的时间复杂度。所以总的重建堆的时间复杂度为O(）。

                3、堆排序总结
        1、以升序为例：先找到最后一个非叶节点，采用向下调整算法，再找到倒数第二个非叶节点，重复向下调整算法。

动图如下：

        2、将数组调整成大堆后，将堆顶数据（最大的数）和堆底数据进行互换，锁定这个最大的数。这个时候原有的堆形态被破坏，需要重新使用向下调整算法对这个数组重建堆。迭代锁定。

动图如下：

        3、向上不如向下是因为第一次建堆效率向下高O(N),原因：

最后一层向下不用考虑

向下算法越往节点多的层，调整次数越少，向上则相反。

        4、堆排序初始化堆的时间复杂度为O(N),后续重建堆的时间复杂度为O(N*logN),所以总体复杂度为N+N*logN，即O(N*logN)