21天学习挑战赛-树形选择排序和堆排序

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

树形选择排序

树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort), 是一种按照锦标赛的思想进行选择排序的方法。首先对 $n$ 个记录的关键字进行两两比较，然后在其中 $\lceil \frac{n}{2}\rceil$ 个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有 $n$ 个叶子结点的完全二叉树表示。

选择最小关键字

8 个叶子结点中依次存放排序之前的 8 个关键字，每个非终端结点中的关键字均等于其左、右孩子结点中较小的关键字，则根结点中的关键字即为叶子结点中的最小关键字。

选择次小关键字

在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字（13) 改为“最大值”，然后从该叶子结点开始，和其左（或右）兄弟的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次小关键字。

选择从小到大的所有关键字

同理，可依次选出从小到大的所有关键字。

复杂度分析

由于含有 $n$ 个叶子结点的完全二叉树的深度为 $\lceil {\log }_{2}n\rceil +1$, 则在树形选择排序中，除了最小关键字之外，每选择一个次小关键字仅需进行 $\lceil {\log }_{2}n\rceil$ 次比较，因此，它的时间复杂度为 $O(nlogn)$。

但是，这种排序方法尚有辅助存储空间较多、和“最大值”进行多余的比较等缺点。为了弥补，威洛姆斯（J. Willioms）在 1964 年提出了另一种形式的选择排序一堆排序。

堆排序

堆排序（Heap Sort）只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

1. 堆的定义

堆的定义如下：$n$ 个元素的序列 $k_1,k_2,\cdots ,k_n$ 当且仅当满足下关系时，称之为堆:

$\begin{array}{cc}{k}_i⩽k_{2i}& \text{ 或 }\{\begin{array}{l}{k}_i⩾k_{2i}\\ k_i⩾k_{2i+1}\\ k_i⩽k_{2i+1}\end{array}\\ & \\ & \left(i=1,2,\cdots ,\lfloor \frac{n}{2}\rfloor \right)\end{array}$

2. 堆排序的定义

若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列 $k_1,k_2,\cdots ,k_n$ 是堆，则堆顶元素（或完全二叉树的根）必为序列中 $n$ 个元素的最小值（或最大值）。

3. 堆排序要解决的问题

由此，实现堆排序需要解决两个问题：

$(1)$ 如何由一个无序序列建成一个堆？
$(2)$ 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

4. 算法代码

堆排序的算法如算法 10.11 所示，其中筛选的算法如算法 10.10 所示。

算法 10.10

typedef SqList HeapType;                                //堆采用顺序表存储表示 

void HeapAdjust (HeapType & H, int s, int m){

    //已知 H.r[s..m] 中记录的关键字除 H.r[s].key 之外均满足堆的定义，本函数调整 H..r[s] 的关键字，使 H.r[s..m] 成为一个大顶堆（对其中记录的关键字而言）
    for (j = 2 * S; j <= m; j *= 2){                    //沿 key 较大的孩子结点向下筛选 
        
        if(j < m && LT(H.r[j].key, H.r[j + 1].key))
            ++j;                                        //j 为 key 较大的记录的下标 
        
        if (!LT(rc.key, H.r[j].key)                     //rc 应插入在位置 s 上
            break;

        H.r[s] = H.r[j]; 

        s = j;
    }
    
    H.r[s] = rc;                                        //插入 

}// HeapAdjust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法 10.11

void HeapSort(HeapType & H){                            //对顺序表 H 进行堆排序 

    for(i = H.length / 2; i > 0; -- i)                  //把 H.r[1..H.length] 建成大顶堆

        HeapAjust (H, i, H.length);

    for(i = H.length; i > 1; --i){

        H.r[1] <--> H.r[i];                             //将堆顶记录和当前未经排序子序列 Hr[1..i] 中，最后一个记录相互交换

        HeapAjust (H, 1, i - 1);                        //将 H.r[1..i - 1] 重新调整为大顶堆
    }
}//HeapSort
1
2
3
4
5
6
7
8
9
10
11
12
13

为使排序结果和 10.1 节中的定义一致，即：使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶雄”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前 $n-1$ 记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。由此，“筛选”应沿关键字较大的孩子结点向下进行。

5. 复杂度分析

堆排序方法对记录数较少的文件并不值得提倡，但对 $n$ 较大的文件还是很有效的因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

对深度为 $k$ 的堆，筛选算法中进行的关键字比较次数至多为 $2(k-1)$ 次，则在建含 $n$ 个元素、深度为 $h$ 的堆时，总共进行的关键字比较次数不超过 $4n$。

由第 i 层上的结点数至多为 $2^{i-1}$，以它们为根的二叉树的深度为 $h-i+1$, 则调用 $\lfloor \frac{n}{2}\rfloor$ 次 HeapAdjust 过程时总共进行的关键字比较次数不超过下式之值:

$\begin{array}{r}\sum _{i=h-1}^1{2}^{i-1}\cdot 2(h-i)=\sum _{i=h-1}^1{2}^i\cdot (h-i)=\sum _{j=1}^{h-1}{2}^{h-j}\cdot j⩽(2n)\sum _{j=1}^{h-1}j/2^j⩽4n\end{array}$

又，$n$ 个结点的完全二叉树的深度为 $\lfloor {\log }_{2}n\rfloor +1$, 则调整建新堆时调用 HeapAdjust 过程 $n-1$ 次，总共进行的比较次数不超过下式之值:

$2\left({\log }_2(n-1)\right]+\lfloor {\log }_2(n-2)\rfloor +\cdots +{\log }_{2}2)<2n\left(\lfloor {\log }_{2}n\rfloor \right)$

由此，堆排序在最坏的情况下，其时间复杂度也为 $O(nlogn)$。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。