79数据结构第七章排序7.4堆排序 79数据结构第七章排序7.4堆排序

树形选择排序的时间复杂度为O(nlog，n)。

树形选择是一种稳定的排序算法。这是它的分析。接下来再看堆排序，其实堆排序类似于前面的塑形排序。

先看这，这其实就是什么叫堆，大家还有印象吗？最小堆跟最大堆的概念。最小堆最小值一定在次堆顶元素，最大堆的最大值一定在堆顶元素，所以这里面是小堆。这种像小点堆其实都一样的，有的地方称为最小堆，有的称叫最大堆，那是小堆，大点堆。

这看成是这个，这里面所有非中节点的一说实话就是这个意思。什么意思？给大家说解释一下，这个节点就是在我这小堆里面，这个节点一定要大于它两个止节点，这是最小堆。如果最大堆的就是它，一定要带有它两个止节点，这是最小的最大堆的概念。

接下来看相应的题目，比如这个，它是一个最小堆，从这里知道第一个也是最小的，这里写出来，这个大于它，这两个写小于这两个，这个也小，这两个小于这两个，这个叫最小堆。小点堆，这个是它不是堆。

继续看这个，为什么不是堆？首先有个14，14不会比98跟81小，所以这个有它。比如这个，我发现27并不是比14根比14小了，所以它就不是堆，当然它也不是最大堆。因为如果最大堆要求什么？这个要大于这两个，但是它没有。

堆排序的算法是什么？首先将待排序的记录，这个堆排序有点类似前面的数的排列，当然或者选择排序。选择排序首先将待排序的记录对应成一颗完全或差数，并把它转变成初始堆，也就是首先建初始堆。这个时候根节点具有最大或者是最小的关键字值，再去交换根节点和最后一个节点的位置。

除了第一个节点之外，前面n减一个节点仍然能够构成完全无差数，再把它们调整成对，同样交换根节点和最后一个节点，一直这样交换下去就可以得到最后一个根节点为止，必须得到有区别。

这两个问题第一个是如何建初始堆，第二个是如何进行筛选。建初始堆其实前面有先，所谓"筛选"指的是对一棵左/右子树均为堆的完全二叉树，"调整"根结点使整个二叉树也成为一个堆。

首先先看见筛选是什么？就是对一个左右指数均为堆的完全和差数调整它的根结点，使它成为一个堆。像这情况，一个堆进行调整，然后进行筛选，这里面是一个大点堆，在这个地方要注意98跟12进行互换就不是堆了，所以这个时候要进行调整或者进或者进行筛选。

怎么筛选的问题？这比较比较，这个就是堆的运算，用筷子过一下，见堆是从下到上进行筛选，或者有的地方将侧面就调整，是一个从下到上进行筛选的过程，就是这样一个选这样一个过程，这是一个间对运算的内容，这其实就是奥差数，在奥差数一个知识点里面会提到过。

这个堆排序过程这里或者过一下。接下来看一下堆排序的时间复杂度的分析。首先最多比较次数是2K减1，然而对n个关键字建成深度为h等于这个的堆所需要进行的关键字的比较的次数最多是c，然后调整堆顶n减一次，需要自己进行的操作次数不超过这么多。

看它的算法直接是这样得到的。对排序的时间复杂度分析，对深度为k的堆筛选所进行的关键字最多为2k减1，看这2，这个对最多的是4N，这个的最多是一个这么多。

对于排序的时间复杂度是这个，注意这个地方大家会发现它的时间复杂度是比较优异的。前面就是冒花排序，各种之类的可能都是在这一块，所以这种基本上是在排序算法里面比较优异的一种算法。前面的快速排序也差不多是这种方式。

对于排序的时间复杂度，首先看一下它是这个，而它所需的辅助空间只要一个，然后这里面这种不稳定的排序。接下来再看看叫做规并排序。