树和堆 —— 跟WilliamYan一起学算法

大家好!欢迎来到《跟WilliamYan一起学算法》。我是你们的老朋友,W_YXN.
之前我们读过这篇文章,里面提到了“堆”的概念。昨天我们也学习了图论基础,而“树”是“图”的一类特例。那么,今天我们就来学习“树”和“堆”这两个非常重点的概念吧。

定义

树是图的特例

不包含圈的图称为无圈图(acyclic graph);连通的无圈图称为(tree),常用字母T表示

  • 设无向图G(V,E)=(V,E)的顶点数为n,边数为m,则下列命题等价:

    1. G是树
    2. G中任意两顶点间有且仅有一条路相连
    3. G是连通的,且m=n-1
    4. G中无圈,且m=n-1
    5. G中无圈,但在G中任意不相邻的两顶点间增加一条边,就得到唯一一个圈

由k棵树组成的森林满足:m=n-k,其中n为G的顶点数,m为G的边数。

由于树是一种特别有用的数据结构,因此,它有着一些自身的特点和概念:

一、节点(node)

就是图(graph)的顶点(vertex)。如上图中的顶点:0,1,2,3,4,5,6,7,8。

二、枝(branch)

就是图(graph)的边(edge)。如上图中的0->1, 0->3, 0->5, 1->2, 1->4, 3->6, 5->8, 8->7。

三、根(root)

一颗树可以想象成从某一个顶点开始进行分枝,那么这个顶点就是“根”。一颗树的每一个节点都可以作为根。如图中可以将节点0作为根。
《树和堆 —— 跟WilliamYan一起学算法》

四、叶(leaf)

在一颗树上选定根后,如节点0作为根。由根开始不断分枝,途中所有无法再分枝的节点成为叶。如下图中,根为点0,则节点2,4,6,7是叶。

《树和堆 —— 跟WilliamYan一起学算法》

一棵阶大于或等于2的树至少有两片树叶

五、度(degree)

一个节点拥有的子树数称为节点的度(degree)。下图中,根节点0有3个子树,度为3;节点1有2个子树,度为2;节点3,5分别只有一个子树,度为1。叶(leaf)也可以用度来定义:度为0的节点称为叶(leaf)。节点2,4,6,7没有子树,度为0,所以2,4,5,7为叶。

《树和堆 —— 跟WilliamYan一起学算法》

所有节点的度的最大值称为该树的度。

六、层/深度/高度(level/depth/height)

在一颗树中选定根(root)后,按照每个点离根的距离,可以将树中的点分为多个层级。

《树和堆 —— 跟WilliamYan一起学算法》

而一个树的最大层级数称为树的深度(depth)或高度(height),如该树的深度(高度)为4。一个节点到下方的叶的最大层级数之差称为节点的高度(height),如节点1位于层1,下方的叶子2,4位于层2,所以节点1的高度是1;同理,节点3的高度也是1,节点5的高度是2,节点2本身是叶,其高度是0,根节点0的高度是3。

七、双亲/孩子/兄弟(parent/child/sibling)

在一颗树中选定根(root)后,相邻的两点,靠近根的是双亲(parent),远一点的是孩子(child)。

《树和堆 —— 跟WilliamYan一起学算法》

如上图中,0是1的双亲(parent),2,4是1的孩子(child)。2,4有共同的双亲,因此2,4之间互称为兄弟(sibling)。
同样的,3是6的双亲,6是3的孩子;5是8的双亲,8是5的孩子。1,3,5是0的孩子,1,3,5互称为兄弟。

八、祖先/后代(ancestor/descendant)

在一颗树中选定根(root)后,一个点的双亲、双亲的双亲、……都是此点的祖先(ancestor),根节点是所有子节点的祖先,注意双亲(parent)也属于祖先。因此,祖先是一个集合概念。同理,一个点的孩子、孩子的孩子、……都是此点的后代(descendant),后代也是一个集合概念。

九、森林(forest)

很多颗树的集合称为森林。森林中,树与树之间互不相交。

《树和堆 —— 跟WilliamYan一起学算法》

此外,与图一样,树也有“有向/无向”,“同构”,“权重”,“路径”等概念,含义与图类似,不再赘述。

最后总结下:

  1. 树中所有点都是连通的;
  2. 树中任意2点之间只有唯一一条路径;
  3. 树是无环的连通图;
  4. 森林是无环的非连通图。

=[定义 参考01]: https://blog.csdn.net/yyywww666/article/details/50377546 "图论中树的基本概念总结"
=[定义 参考02]: https://blog.csdn.net/saltriver/article/details/54428750 "图论(二)树"

存储

目前主要有以下几种存储方式:

1、双亲表示法:

  • 实现:通常用一个二维数组,在存储结点的同时也将对应节点的父节点存储进来。
  • 特点:找父节点容易、找子节点难。

《树和堆 —— 跟WilliamYan一起学算法》

2、 孩子表示法:

  • 实现:每个结点都存储在一个二维数组的第一列里面,多个子节点之间以链表方式连接,最后一个子节点的指向为NULL,数组的第二个元素指向其子节点链表的起始地址。
  • 特点:找子节点容易,找父节点难。

    《树和堆 —— 跟WilliamYan一起学算法》

3、 双亲孩子表示法:

  • 实现:将双亲表示法与孩子表示法综合起来,既存储父节点的下标,又指向子节点链表。
  • 特征:找父节点与子节点都比较方便,但相对前面两种复杂度有一定程度的提升。

    《树和堆 —— 跟WilliamYan一起学算法》

=[存储 参考01]: https://www.cnblogs.com/tarbitrary/p/4030652.html "树的定义、分类及存储"

二叉树

定义

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。

《树和堆 —— 跟WilliamYan一起学算法》

性质

  1. 二叉树第$i$ 层上的结点数目最多为 $2^{i-1}(i\geq 1)$
  2. 深度为$k$ 的二叉树至多有 $2^k-1$ 个结点 $(k \geq 1)$
  3. 包含$n$个结点的二叉树的高度至少为$(\log_2 n)+1$
  4. 在任意一棵二叉树中,若终端结点的个数为$n_0$,度为2的结点数为$n_2$,则$n_0=n_2+1$

性质4的证明

因为二叉树中所有结点的度数均不大于2,不妨设$n_0$表示度为0的结点个数,$n_1$表示度为1的结点个数,$n_2$表示度为2的结点个数。三类结点加起来为总结点个数,于是便可得到: $n=n_0+n_1+n_2$ (1)

由度之间的关系可得第二个等式: $n=n_0\times 0+n_1\times 1+n_2\times 2+1$ 即 $n=n_1+2n_2+1$ (2)

将(1)(2)组合在一起可得到 $n_0=n_2+1$

特殊的二叉树及特点

斜树

所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)。这就是斜树,应用较少

《树和堆 —— 跟WilliamYan一起学算法》
《树和堆 —— 跟WilliamYan一起学算法》

满二叉树

所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树。就是完美圆满的意思,关键在于树的平衡。

《树和堆 —— 跟WilliamYan一起学算法》

根据满二叉树的定义,得到其特点为:

  1. 叶子只能出现在最下一层。
  2. 非叶子结点度一定是2.
  3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多。
完全二叉树

对一棵具有n个结点的二叉树按层序排号,如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同,就是完全二叉树。满二叉树必须是完全二叉树,反过来不一定成立。

其中关键点是按层序编号,然后对应查找。

《树和堆 —— 跟WilliamYan一起学算法》

在上图中,树1,按层次编号5结点没有左子树,有右子树,10结点缺失。树2由于3结点没有字数,是的6,7位置空挡了。树3中结点5没有子树。

《树和堆 —— 跟WilliamYan一起学算法》

上图就是一个完全二叉树。

结合完全二叉树定义得到其特点:

  1. 叶子结点只能出现在最下一层(满二叉树继承而来)
  2. 最下层叶子结点一定集中在左 部连续位置。
  3. 倒数第二层,如有叶子节点,一定出现在右部连续位置。
  4. 同样结点树的二叉树,完全二叉树的深度最小(满二叉树也是对的)。

根据下图加深理解,什么时候是完全二叉树。

《树和堆 —— 跟WilliamYan一起学算法》

完全二叉树性质
  1. 具有n的结点的完全二叉树的深度为$\log_2n+1$.

    满二叉树是完全二叉树,对于深度为k的满二叉树中结点数量是$2^k-1 = n$,完全二叉树结点数量肯定最多$2^k-1$,同时完全二叉树倒数第二层肯定是满的(倒数第一层有结点,那么倒是第二层序号和满二叉树相同),所以完全二叉树的结点数最少大于少一层的满二叉树,为$2^{k-1}-1$。

    根据上面推断得出: $2^{k-1}-1< n\leq 2^k-1$,因为结点数$n$为整数那么$n\leq 2^k-1$可以推出$n\leq 2^k ,n>2^{k-1}-1$可以推出$ n\geq 2^{k-1}$,所以$2^{k-1}<n\leq 2^k$ 。即可得$k-1\leq \log_2 n<k$ 而k作为整数因此$k=[\log_2 n]+1$。

  2. 如果有一颗有n个节点的完全二叉树的节点按层次序编号,对任一层的节点$i(1\leq i\leq n)$有

    • 如果$i=1$,则节点是二叉树的根,无双亲,如果$i>1$,则其双亲节点为$[i/2]$,向下取整
    • 如果$2i>n$那么节点i没有左孩子,否则其左孩子为$2i$
    • 3.如果$2i+1>n$那么节点没有右孩子,否则右孩子为$2i+1$

《树和堆 —— 跟WilliamYan一起学算法》

在上图中验证

第一条:

当$i=1$时,为根节点。当$i>1$时,比如结点为7,他的双亲就是$7\div 2= 3$

第二条:

结点6,$6\times 2 = 12>10$,所以结点6无左孩子,是叶子结点。结点5,$5\times 2 = 10$,左孩子是10

第三条:

结点5,$2\times 5+1>10$,则没有右孩子

存储

顺序存储结构

《树和堆 —— 跟WilliamYan一起学算法》

使用顺序存储结构,对完全二叉树这种结构是非常合适的。可以按照从上之下,从左至右顺序存储n个结点的完全二叉树的结点父子关系

《树和堆 —— 跟WilliamYan一起学算法》

完全二叉树的这种存储结构,有以下特点

  • 非根节点(序号i>1)的父节点序号(数组下标)是 i/2 (取整)。
  • 结点(序号为i)的左孩子结点的序号是2i,如果2i>n,则没有左孩子;
  • 结点(序号为i)的右孩子结点的序号是2i+1,如果2i+1>n,则没有右孩子。

一般普通的二叉树,在其空余位置补充控制,当做是完全二叉树,采用数组结构存储,将导致存储空间的浪费。

链式存储结构

二叉树的链式存储结构中,每一个结点包含三个关键属性:指向左子树的指针,数据域,指向右子树的指针;根据这个叙述,我们可以按如下结构定义结点。

《树和堆 —— 跟WilliamYan一起学算法》

代码略。

定义

堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

堆(heap)也被称为优先队列(priority queue)。队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。而堆也是一样,在堆底插入元素,在堆顶取出元素,但是堆中元素的排列不是按照到来的先后顺序,而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。如图一所示就是一个堆,堆优先顺序就是大的元素排在前面,小的元素排在后面,这样得到的堆称为最大堆。最大堆中堆顶的元素是整个堆中最大的,并且每一个分支也可以看成一个最大堆。同样的,我们可以定义最小堆,如图二所示。

《树和堆 —— 跟WilliamYan一起学算法》

若无特别声明,我们下面讨论的是最大堆

当一颗二叉树的每个结点都大于等于它的两个子节点时,它被称为堆有序。相应地,在堆有序的二叉树中,每个结点都小于等于它的父节点,从任意结点往上,我们都能得到一列非递减的元素;从任意结点往下,我们都能得到一列非递增的元素。根节点就是堆有序的二叉树中的最大节点。所以说在一个堆有序的二叉树中,父节点的位置是K/2,它的两个子节点的位置是2k,2k+1。这样通过索引的变化,我们就可以在数组中得到不同的元素了。

在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。

例子:

《树和堆 —— 跟WilliamYan一起学算法》

这是一个最大堆,,因为每一个父节点的值都比其子节点要大。1072 都大。751都大。

根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常的有用,因为堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。

注意:堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。

=[定义 参考]: https://blog.csdn.net/qq_33186366/article/details/51876191 "数据结构之堆的定义"

存储

用数组来实现树相关的数据结构也许看起来有点古怪,但是它在时间和空间上都是很高效的。

我们准备将上面的例子中的树这样存储:

[ 10, 7, 2, 5, 1 ]

如果我们不允许使用指针,那么我们怎么知道哪一个节点是父节点,哪一个节点是它的子节点呢?问得好!节点在数组中的位置index 和它的父节点已经子节点的索引之间有一个映射关系。

如果 i 是节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。

我们将公式放到前面的例子中验证一下。

《树和堆 —— 跟WilliamYan一起学算法》

注意:根节点(10)没有父节点,因为 -1 不是一个有效的数组索引。同样,节点 (2)(5)(1) 没有子节点,因为这些索引已经超过了数组的大小,所以我们在使用这些索引值的时候需要保证是有效的索引值。

复习一下,在最大堆中,父节点的值总是要大于(或者等于)其子节点的值。这意味下面的公式对数组中任意一个索引 i都成立:

array[parent(i)] >= array[i]

可以用上面的例子来验证一下这个堆属性。

如你所见,这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂,但这就是交易:我们节约了空间,但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。

理解数组索引和节点位置之间的关系非常重要。这里有一个更大的堆,它有15个节点被分成了4层:

《树和堆 —— 跟WilliamYan一起学算法》

《树和堆 —— 跟WilliamYan一起学算法》

图片中的数字不是节点的值,而是存储这个节点的数组索引!这里是数组索引和树的层级之间的关系:

《树和堆 —— 跟WilliamYan一起学算法》

由上图可以看到,数组中父节点总是在子节点的前面。

注意这个方案与一些限制。你可以在普通二叉树中按照下面的方式组织数据,但是在堆中不可以:

《树和堆 —— 跟WilliamYan一起学算法》

在堆中,在当前层级所有的节点都已经填满之前不允许开是下一层的填充,所以堆总是有这样的形状:

《树和堆 —— 跟WilliamYan一起学算法》

注意:你可以使用普通树来模拟堆,但是那对空间是极大的浪费。

堆属性适用于每一个节点,因为父节点总是比它的字节点小。(你也可以验证一下:一个从高到低有序排列的数组是一个有效的最大堆)

注意:并不是每一个最小堆都是一个有序数组!要将堆转换成有序数组,需要使用堆排序。

=[存储 来源]: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Heap "Heap"

=[翻译版本]: https://www.jianshu.com/p/6b526aa481b1 "数据结构:堆(Heap)"

更多数学公式

如果你好奇,这里有更多的公式描述了堆的一些确定属性。你不需要知道这些,但它们有时会派上用场。 可以直接跳过此部分!

树的高度是指从树的根节点到最低的叶节点所需要的步数,或者更正式的定义:高度是指节点之间的边的最大值。一个高度为 h 的堆有 h+1 层。

下面这个对的高度是3,所以它有4层:

《树和堆 —— 跟WilliamYan一起学算法》

如果一个堆有 n 个节点,那么它的高度是 h = floor(log2(n))。这是因为我们总是要将这一层完全填满以后才会填充新的一层。上面的例子有 15 个节点,所以它的高度是 floor(log2(15)) = floor(3.91) = 3

如果最下面的一层已经填满,那么那一层包含 2^h 个节点。树中这一层以上所有的节点数目为 2^h – 1。同样是上面这个例子,最下面的一层有8个节点,实际上就是 2^3 = 8。前面的三层一共包含7的节点,即:2^3 - 1 = 8 - 1 = 7

所以整个堆中的节点数目为:2^(h+1) – 1。上面的例子中,2^4 - 1 = 16 - 1 = 15

叶节点总是位于数组的 floor(n/2)n-1 之间。

用途与操作

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆:

  • shiftUp(): 如果一个节点比它的父节点大(最大堆)或者小(最小堆),那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
  • shiftDown(): 如果一个节点比它的子节点小(最大堆)或者大(最小堆),那么需要将它向下移动。这个操作也称作“堆化(heapify)”。

shiftUp 或者 shiftDown 是一个递归的过程,所以它的时间复杂度是 O(log n)

基于这两个原始操作还有一些其他的操作:

  • insert(value): 在堆的尾部添加一个新的元素,然后使用 shiftUp 来修复对。
  • remove(): 移除并返回最大值(最大堆)或者最小值(最小堆)。为了将这个节点删除后的空位填补上,需要将最后一个元素移到根节点的位置,然后使用 shiftDown 方法来修复堆。
  • removeAtIndex(index): 和 remove() 一样,差别在于可以移除堆中任意节点,而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown(),如果与父节点比较发现无序则使用 shiftUp()
  • replace(index, value):将一个更小的值(最小堆)或者更大的值(最大堆)赋值给一个节点。由于这个操作破坏了堆属性,所以需要使用 shiftUp() 来修复堆属性。

上面所有的操作的时间复杂度都是 O(log n),因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间:

  • search(value):堆不是为快速搜索而建立的,但是 replace()removeAtIndex() 操作需要找到节点在数组中的index,所以你需要先找到这个index。时间复杂度:O(n)
  • buildHeap(array):通过反复调用 insert() 方法将一个(无序)数组转换成一个堆。如果你足够聪明,你可以在 O(n) 时间内完成。
  • 堆排序:由于堆就是一个数组,我们可以使用它独特的属性将数组从低到高排序。时间复杂度:O(n lg n)

堆还有一个 peek() 方法,不用删除节点就返回最大值(最大堆)或者最小值(最小堆)。时间复杂度 O(1)

注意:到目前为止,堆的常用操作还是使用 insert() 插入一个新的元素,和通过 remove()移除最大或者最小值。两者的时间复杂度都是O(log n)。其其他的操作是用于支持更高级的应用,比如说建立一个优先队列。

插入

我们通过一个插入例子来看看插入操作的细节。我们将数字 16 插入到这个堆中:

《树和堆 —— 跟WilliamYan一起学算法》

堆的数组是: [ 10, 7, 2, 5, 1 ]

第一股是将新的元素插入到数组的尾部。数组变成:

[ 10, 7, 2, 5, 1, 16 ]

相应的树变成了:

《树和堆 —— 跟WilliamYan一起学算法》

16 被添加最后一行的第一个空位。

不行的是,现在堆属性不满足,因为 216 的上面,我们需要将大的数字在上面(这是一个最大堆)

为了恢复堆属性,我们需要交换 162

《树和堆 —— 跟WilliamYan一起学算法》

现在还没有完成,因为 10 也比 16 小。我们继续交换我们的插入元素和它的父节点,直到它的父节点比它大或者我们到达树的顶部。这就是所谓的 shift-up,每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。

最后我们得到的堆:

《树和堆 —— 跟WilliamYan一起学算法》

现在每一个父节点都比它的子节点大。

删除根节点

我们将这个树中的 (10) 删除:

《树和堆 —— 跟WilliamYan一起学算法》

现在顶部有一个空的节点,怎么处理?

《树和堆 —— 跟WilliamYan一起学算法》

当插入节点的时候,我们将新的值返给数组的尾部。现在我们来做相反的事情:我们取出数组中的最后一个元素,将它放到树的顶部,然后再修复堆属性。

《树和堆 —— 跟WilliamYan一起学算法》

现在来看怎么 shift-down (1)。为了保持最大堆的堆属性,我们需要树的顶部是最大的数据。现在有两个数字可用于交换 72。我们选择这两者中的较大者称为最大值放在树的顶部,所以交换 71,现在树变成了:

《树和堆 —— 跟WilliamYan一起学算法》

继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于我们的堆,我们只需要再有一次交换就恢复了堆属性:

《树和堆 —— 跟WilliamYan一起学算法》

=[用途与操作 来源]: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Heap "Heap"

=[翻译版本]: https://www.jianshu.com/p/6b526aa481b1 "数据结构:堆(Heap)"

C++ STL priority_queue

基本操作

push(x) 将x压入队列

pop() 弹出队列的第一个元素(队顶元素),注意此函数并不返回任何值

front() 返回第一个元素(队顶元素)

back() 返回最后被压入的元素(队尾元素)

empty() 当队列为空时,返回true

size() 返回队列的长度

堆排序

定义

  堆排序是利用这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为$O(n\log_2 n)$,它也是不稳定排序。首先简单了解下堆结构。

基本思想及步骤

  堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。

  a.假设给定无序序列结构如下

《树和堆 —— 跟WilliamYan一起学算法》

2.此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。

《树和堆 —— 跟WilliamYan一起学算法》

4.找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

《树和堆 —— 跟WilliamYan一起学算法》

这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。

《树和堆 —— 跟WilliamYan一起学算法》

此时,我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

《树和堆 —— 跟WilliamYan一起学算法》

b.重新调整结构,使其继续满足堆定义

《树和堆 —— 跟WilliamYan一起学算法》

c.再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.

《树和堆 —— 跟WilliamYan一起学算法》

后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

《树和堆 —— 跟WilliamYan一起学算法》

再简单总结下堆排序的基本思路:

  1. 将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
  2. 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端
  3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序

动图

《树和堆 —— 跟WilliamYan一起学算法》

=[堆排序 来源]: https://www.cnblogs.com/chengxiao/p/6129630.html "图解排序算法(三)之堆排序"

总结

树和堆是OI比赛中十分基础的知识点。
许多时候,都是OI竞赛中的一大考点。虽然可以轻易地使用Priority_queue解决,但是树是必须学会的。到了后期,我们还会学习树形DP之类的知识点,因此打好坚实的基础是非常有必要的。

© 2019 WilliamYan
Some rights reserved.


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据