二叉树-堆(一)

二叉树 (一)

树概念及结构 (维基百科参考)

1树的概念

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

• 有一个特殊的结点，称为根结点，根结点没有前驱结点(没有父节点);

• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继;

• 每个节点都只有有限个子节点或无子节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

• 树里面没有环路(cycle)

• 因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树的相关概念/术语:

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

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

• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I、P、Q、K、L、M、N等节点为叶节点

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

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

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

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

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

• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

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

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

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

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

2.树的种类

有序/无序：

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。

• 有序树/搜索树/查找树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。即树的所有节点按照一定的顺序排列，这样进行插入、删除、查找时效率就会非常高

平衡/不平衡：

• 平衡树

  • 绝对平衡树：所有叶节点在同一层

  • 非绝对平衡树

• 不平衡树

节点的分叉情况：

• 等叉树：是每个节点的键值个数都相同、子节点个数也都相同

  • 二叉树：每个节点最多含有两个子树的树称为二叉树；

    • 完全二叉树：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

    • 满二叉树：所有叶节点都在最底层的完全二叉树；

    • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

    • 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；

  • 霍夫曼树：带权路径最短的二叉树称为霍夫曼树或最优二叉树；

  • 多叉树

• 不等叉树：每个节点的键值个数不一定相同、子节点个数也不一定相同

  • B树家族：对不等叉树的节点键值数和插入、删除逻辑添加一些特殊的要求，使其能达到绝对平衡的效果。B树全称Balance Tree。如果某个B树上所有节点的分叉数最大值是m，则把这个B数叫做m阶B树。

 

树的家族:(暂作了解)

 

二叉树	二叉搜索树 笛卡尔树 MVP树 Top tree T树 线索二叉树
堆	二叉堆 二项堆 斐波那契堆 左偏树 配对堆 斜堆 范恩德蟒蛇树
自平衡二叉查找树	AA树 AVL树 左倾红黑树 红黑树 替罪羊树 伸展树 树堆 加权平衡树
B树	B+树 B*树 Bx树 UB树 2-3树 2-3-4树 (a,b)-树 跳舞树 H树
Trie	后缀树 基数树 三叉查找树 X-快速前缀树 Y-快速前缀树 AC自动机
二叉空间分割（BSP）树	四叉树 八叉树 k-d树 隐式k-d树 VP树
非二叉树	指数树 融合树 PQ树 SPQR树
空间数据分割树	R树 R*树 R+树 X树 M树 线段树 (存储区间) 线段树 (区间查询) 可持久化线段树 希尔伯特R树 优先R树
其他树	散列日历 散列树 手指树 顺序统计树 度量树 覆盖树 BK树 二重连锁树 iDistance Link-cut tree Log-structured merge-tree 树状数组 哈希树

 

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来会稍显麻烦，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：父节点表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

孩子兄弟表示法(左兄弟右孩子)

xxxxxxxxxx
7
1
typedef int DataType;
2
struct Node
3
{
4
 struct Node* _firstChild1; // 第一个孩子结点
5
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
6
 DataType _data; // 结点中的数据域
7
};

父节点表示法

xxxxxxxxxx
12
1
/* 树节点的定义 */
2
#define MAX_TREE_SIZE 100
3
typedef struct
4
{
5
TElemType data;
6
int parent; /* 父节点位置域 */
7
} PTNode;
8
typedef struct
9
{
10
PTNode nodes[MAX_TREE_SIZE];
11
int n; /* 节点数 */
12
} PTree;

孩子链表表示法

xxxxxxxxxx
13
1
/*树的孩子链表存储表示*/
2
typedef struct CTNode { // 孩子节点
3
int child;
4
struct CTNode *next;
5
} *ChildPtr;
6
typedef struct {
7
ElemType data； // 节点的数据元素
8
ChildPtr firstchild； // 孩子链表头指针
9
} CTBox;
10
typedef struct {
11
CTBox nodes[MAX_TREE_SIZE]；
12
int n, r； // 节点数和根节点的位置
13
} CTree;

4.树在实际中的应用

1. 文件系统

文件系统是树结构应用最为广泛的例子之一。在文件系统中，所有文件和目录都被组织成一棵树，其中每个目录项可以是一个文件（叶节点）或一个包含其他文件/目录的目录（内部节点）。Windows的文件系统是森林结构

2. 数据库索引

数据库使用树结构（特别是B树和B+树）来索引数据，这样可以极大地提高数据的查询速度。树结构允许数据库在对数据进行增加、删除、查找操作时保持元素有序，从而快速定位到指定的数据。

3. 网络路由

树结构，尤其是前缀树（Trie）和最小生成树，广泛用于网络路由算法中。它们帮助在网络中有效地寻找目的地路径，优化数据包的传输。

4. 图形界面(GUI)组件

许多图形用户界面（GUI）框架使用树结构来组织和管理界面组件。例如，窗口中的按钮、文本框等控件可以被组织成树状结构，以表示它们之间的层级和包含关系。

5. 语言处理

在编译原理中，抽象语法树（AST）是源代码的树形表示，用于语法分析和其他编译过程。树结构允许编译器理解和处理编程语言的结构。

6. 决策树

在机器学习领域，决策树用于分类和回归任务。它通过学习数据特征的层次结构来做出预测或决策，是一种直观且广泛使用的算法。

7. 游戏编程

在游戏开发中，场景图（Scene Graph）通常用树结构来组织和管理游戏对象及其关系。此外，AI决策过程中也常用树结构，如行为树（Behavior Tree）用于模拟复杂的决策过程。

8.Houdini数据结构

• 层级组织：Houdini中的节点以层级的方式组织，形成了一种树状结构。这种结构使得复杂的场景管理变得更加直观和有序。顶层节点可以是对象节点（Object Nodes），它们可以包含更多子节点，如几何节点（Geometry Nodes），从而构建出复杂的场景层次。

• 父子关系：在这种树状结构中，每个节点都可以有子节点（或被视为叶子节点，即没有子节点）。这种父子关系不仅有助于组织场景，而且还影响了节点间的继承关系，比如变换的继承。

• 路径：在Houdini中，每个节点都可以通过其在树状结构中的路径进行访问，类似于文件系统中的路径。这个路径反映了节点在树中的位置，从而方便用户定位和引用场景中的特定元素。

二叉树概念

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树的分支具有左右次序，不能随意颠倒。因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 

特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是$2^k-1$$2^k-1$,则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

每一层都是满的就是满二叉树

前k-1层都是满的,最后一层可以不满,但是从左到右是连续的是完全二叉树

	完全二叉树	满二叉树
总节点k	$2^{ℎ-1}<=k<=2^{ℎ}-1$$2^{ℎ&#8722;1}<= k <= 2^ℎ&#8722;1$	$k=2^{ℎ}-1$$k = 2^ℎ&#8722;1$
树高h	$h=lo{g}_{2}k+1$$h =log_2k+1$	$h=lo{g}_2(k+1)$$h =log_2(k+1)$

二叉树的性质:

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有$2^{(i-1)}$$2^{(i-1)}$个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是$2^h-1$$2^h-1$

3. 对任何一棵二叉树, 如果度为0其叶结点个数为$n_0$$n_0$, 度为2的分支结点个数为$n_2$$n_2$,则有$n_0=n_2+1$$n_0=n_2+1$​

   • 公式描述的是二叉树中叶子结点（度为0的结点）和度为2的分支结点之间的关系。

   • 公式 $n_0=n_2+1$$n_0 = n_2 + 1$​ 描述了一个特性，即在任何二叉树中，叶子结点的数量总是比度为2的分支结点的数量多一个。这个关系为什么成立呢？我们通过树的构造来解释：

   • 基础情况：在最简单的情况下，一棵二叉树可能只有一个结点，这个结点即是根也是叶子结点（度为0），此时没有度为2的结点。所以，$n_0=1$$n_0 = 1$ 和 $n_2=0$$n_2 = 0$，满足 $n_0=n_2+1$$n_0 = n_2 + 1$​。

   • 添加结点：当二叉树添加一个新的叶子结点时，要么是增加一个度为0的结点（直接添加到度为1的结点之下也就是添加为子节点，不改变现有叶子结点数量），要么是将一个度为1的结点转变为度为2的结点（这种情况下，新增了一个叶子结点，同时也新增了一个度为2的结点）。在后一种情况下，$n_0$$n_0$ 和 $n_2$$n_2$ 同时增加1，保持了 $n_0=n_2+1$$n_0 = n_2 + 1$​ 的关系不变。

   • 结构保持：无论树如何增长，每次添加度为2的结点时，你都在添加一个新的叶子结点来保持平衡。这是因为在二叉树中，除了最初的根结点外，每个新增的结点都必须连接到一个现有的结点上，这意味着每增加一个度为2的结点，你实际上是在现有的某个叶子结点处分支出去，从而增加了一个新的叶子结点，同时将那个现有的叶子结点转变为一个度为2的结点。

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，$h=lo{g}_2(n+1)$$h=log_2(n+1)$.(PS.$lo{g}_2(n+1)$$log_2(n+1)$是log以2为底，n+1为对数))

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

   1. 若i>0，i位置节点的双亲序号：$(i-1)/2$$(i-1)/2$；

   2. i=0，i为根节点编号，无双亲节点

   3. 若2i+1<n，左孩子序号：2i+1，否则2i+1>=n无左孩子

   4. 若2i+2<n，右孩子序号：2i+2，否则2i+2>=n无右孩子

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

若是满二叉树就能紧凑排列而不浪费空间,然而，它需要连续的存储空间，这样在存储高度为$h$$h$的$n$$n$个节点所组成的一般树时，将浪费很多空间。在最糟糕的情况下，如果深度为h的二叉树其每个节点都只有右孩子，则该存储结构需要占用$2^{ℎ}-1$$2^ℎ−1$的空间，实际上却有$h$$h$个节点，浪费了不少空间，是顺序存储结构的一大缺点。

 

 

2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。 使用链表能避免顺序存储浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。

链式结构又分为二叉链和三叉链，以后写到高阶数据结构如红黑树等会用到三叉链。

xxxxxxxxxx
16
1
  //二叉樹的二叉链表表示
2
  typedef int BTDataType;
3

4
  struct BinaryTreeNode
5
  {
6
      struct BinTreeNode* _pLeft; // 指向当前节点左孩子
7
      struct BinTreeNode* _pRight; // 指向当前节点右孩子
8
      BTDataType _data; // 当前节点值域
9
  }
10

11
  /* 二叉樹的三叉鏈表存儲表示 */
12
   typedef struct BiTPNode
13
   {
14
     BTDataType data;  // 当前节点值域
15
     struct BiTPNode *parent,*lchild,*rchild; /* 父、左右孩子指針 */
16
   }BiTPNode,*BiPTree;

 

二叉树的顺序结构及实现

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

堆始于J. W. J. Williams在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

如果有一个关键码的集合$K=\{k_0,k_1,k_2,k_3,...,k_{n-1}\}$$K = \{k_0,k_1,k_2,k_3,...,k_{n-1}\}$把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：

$K_i<=K_{2\ast i+1}\text{且}{K}_i<=K_{2\ast i+2}(\text{其}\text{中}i=0,1,2...)$$K_i<=K_{2*i+1}且K_i<=K_{2*i+2}(其中i=0,1,2...)$ 称为小堆(树任何一个父亲都小于或等于孩子)

$K_i>=K_{2\ast i+1}\text{且}{K}_i>=K_{2\ast i+2}(\text{其}\text{中}i=0,1,2...)$$K_i>=K_{2*i+1}且K_i>=K_{2*i+2}(其中i=0,1,2...)$ 称为大堆(树任何一个父亲都大于或等于孩子)

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

堆有许多种高级类型包含了适合制作双端队列的最大—最小堆及制作优先权队列的斐波那契堆等。

 

堆的应用场景:

1.优先队列（Priority Queue）

优先队列是二叉堆的最直接应用之一，它允许插入新元素$O(logN)$$O(logN)$，访问队列中的最大元素（最大堆）或最小元素（最小堆）$O(N)$$O(N)$。这在需要根据元素优先级快速检索元素的场景中非常有用，如任务调度、事件驱动的模拟、服务请求处理等

2. 堆排序（Heap Sort）

堆排序是一种高效的排序算法，利用二叉堆的性质来对元素进行排序。它首先将所有元素插入一个最大堆（或最小堆），然后依次取出堆顶元素，得到的序列就是有序的。这个过程的时间复杂度为$O(N\ast logN)$$O(N*log N)$

3. 图算法

在许多图算法中，如迪杰斯特拉算法（Dijkstra's algorithm）和普里姆算法（Prim's algorithm）等，使用二叉堆来维护顶点的优先级可以大大提高算法的效率。在这些算法中，二叉堆用于快速找到最小（或最大）边或路径

4. 数据流的中位数和分位数

二叉堆可以用来高效计算数据流的中位数或其他分位数。通常，使用两个堆，一个最大堆保存较小的一半元素，一个最小堆保存较大的一半元素，这样堆顶就可以表示中位数或其他相关的分位数

5. 负载均衡和任务调度

在负载均衡和任务调度的应用中，二叉堆可以帮助高效地分配任务。通过维护一个根据任务优先级或负载大小的堆，系统可以快速决定下一个要执行的任务或将任务分配给最不忙的处理器。

6. Top K问题

利用最小堆或最大堆维护一个大小为K的数据结构，可以有效地解决Top K问题，特别是当数据是动态变化时。

 

拿典型的堆排序举例子说明:

N	冒泡排序	堆排序
1000	100W次	1W次
100W	1万亿次	2000W次

对一个有100万个元素的数组排序,冒泡排序最坏的情况下需要执行1万亿次,时间复杂度是$O(N^2)$$O(N^2)$, 堆排序在最坏的情况下需要执行2000万次, 时间复杂度是$O(N\ast logN)$$O(N*logN)$ 二者差距是相当大的.

堆的实现

在之前先把堆较为关键的操作解释一下:

向上调整算法:

也称为上浮,它是用来恢复堆性质的一种方法，通常在插入新元素后使用。

基本原理:在堆中插入一个新元素时，为了保持完全二叉树的形状，新元素总是首先插入到树的最底层最右边的空位上(物理层面就是尾插到最后一个结点)。这种插入可能会违反堆的性质，即新元素可能会大于（或小于，取决于是最大堆还是最小堆）其父节点的值。因此，需要通过向上调整来恢复堆的性质。

步骤:

• 将新元素插入到堆的最后位置

• 和父节点进行比较,如果是最大堆，并且新元素大于其父节点,则需要与父节点交换位置,同理如果是最小堆，并且新元素小于其父节点也需要交换,如果不违反堆的性质则不需要操作

• 如果执行了交换的步骤, 则需要继续向上调整, 而如果过程中一直不满足堆得性质就一直向上调整直到成为根节点.

• 当新元素不再需要与父节点交换时，堆的性质恢复，算法结束。

时间复杂度：堆的向上调整算法的时间复杂度为 $O(lo{g}_n)$$O{(log_n)}$，其中 $n$$n$ 是堆中元素的数量。这是因为堆是一棵完全二叉树，其高度为 $lo{g}_n$$log_n$，最坏的情况下需要从树的最底层调整到根节点。

空间复杂度：$O(1)$$O(1)$​​，因为向上调整过程中，除了原始堆之外，不需要额外的存储空间。

向下调整算法:

也称为下沉, 是在删除堆顶元素或构建堆时常用到的算法

步骤：

• 选择子结点：从当前结点开始，比较它的两个子结点（如果存在的话）。在最大堆中，选择两个子结点中较大的一个；在最小堆中，选择较小的一个。

• 比较和交换：如果选定的子结点满足交换条件（即，在最大堆中子结点大于当前结点，在最小堆中子结点小于当前结点），则将当前结点与选定的子结点交换。

• 递归或迭代：交换后，移动到原子结点的位置（现在是交换后的当前结点），重复步骤1和2，直到当前结点满足堆性质为止，即它不再比它的子结点小（在最大堆中）或大（在最小堆中）。

• 结束条件：当当前结点没有子结点或者当前结点已经满足堆性质算法结束。

时间复杂度：堆的向下调整算法的时间复杂度为$O({\log }_n)$$O(\log_n)$, 其中$n$$n$是堆中的元素数量, 堆的高度大约是${\log }_{2}n$$\log_2{n}$​, 在最坏的情况下，需要从堆顶向下调整到堆底。

空间复杂度：$O(1)$$O(1)$，原因同上.

删除堆顶元素

可能首先想到的方式是直接移除堆顶元素, 然后后面的元素向前挪动覆盖, 就像是常规的数组操作. 但是这样做显然有问题的,因为后果就是整个堆层级中父子关系全乱了, 并不能保证还能满足大堆或小堆的性质, 因为向前挪动覆盖数据后, 原先的左子树由兄弟关系变为了右子树的父亲关系, 而左子树和右子树本身是没有大小相关的, 最终可能直接导致失去了堆的性质, 后果就是重新建堆

正确的方法是将堆顶元素和堆的最后一个元素交换,然后堆的大小减一, 最后执行向下调整算法(前提:左子树和右子树符合大堆/小堆)维持堆的性质

堆的插入

先插入到数组的尾上，再进行向上调整算法，直到满足堆。

建堆的方法

1. 自顶向下建堆：

   • 从空堆开始，逐个添加元素。

   • 每添加一个元素，就执行一次向上调整（或“上浮”）操作，以保证新添加的元素满足堆的性质。

   • 这种方法较为直观，但效率不是最高的，特别是在需要建立大型堆时。

   

    

2. 自底向上建堆（更常用、效率更高）：

   • 给定一个无序数组，可以将其视为一个完全二叉树。

   • 从最后一个非叶子节点开始（即最后一个节点的父节点），逐个执行向下调整操作。

   • 按照从下至上、从右至左的顺序对每个非叶子节点执行向下调整，直到根节点。

   • 这个过程只需要线性时间 $O(n)$$O(n)$，因为对于堆中的较低层，虽然节点多，但向下调整的路径短；而对于上层节点，虽然向下调整的路径可能较长，但越往上节点数越少。

 

建堆时间复杂度计算和证明(自底向上建堆方式)

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化, 使用满二叉树来证明(时间复杂度本来看的 就是近似值，多几个节点不影响最终结果)：

假设树的高度为$h$$h$:

第一层, $2^0$$2^0$个节点	需要向下移动$h-1$$h-1$层
第二层, $2^1$$2^1$个节点	需要向下移动$h-2$$h-2$层
第三层, $2^2$$2^2$个节点	需要向下移动$h-3$$h-3$层
第四层, $2^3$$2^3$个节点	需要向下移动$h-4$$h-4$层
.............	.............
第$h-1$$h-1$层, $2^{h-2}$$2^{h-2}$个节点	需要向下移动$1$$1$层
第$h$$h$层, $2^{h-1}$$2^{h-1}$个节点	无需向下移动, 因为它们是叶子节点

则需要移动节点总的步数为:

$T(n)=2^0\ast (h-1)+2^1\ast (h-2)+2^2\ast (h-3)+2^3\ast (h-4)+......+2^{h-3}\ast 2+2^{h-2}\ast 1$$T{(n)}=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+2^3*(h-4)+......+2^{h-3}*2+2^{h-2}*1$​

$2\ast T(n)=2^1\ast (h-1)+2^2\ast (h-2)+2^3\ast (h-3)+2^4\ast (h-4)+......+2^{h-2}\ast 2+2^{h-1}\ast 1$$2*T{(n)}=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+......+2^{h-2}*2+2^{h-1}*1$​

错位相减法:

• $2\ast T(n)=2^1\ast 2^1\ast (h-2)+2^2\ast 2^2\ast (h-3)+2^3\ast 2^3\ast (h-4)+......+2^{h-3}\ast 2^{h-3}\ast 2+2^{h-2}\ast 2^{h-2}\ast 1+2^{h-1}\ast 1$$2*T{(n)}=2^1*2^1*(h-2)+2^2*2^2*(h-3)+2^3*2^3*(h-4)+......+2^{h-3}*2^{h-3}*2+2^{h-2}*2^{h-2}*1+2^{h-1}*1$

• $T(n)=1-h+2^1+2^2+2^3+2^4+...+2^{h-3}+2^{h-2}+2^{h-1}$$T{(n)}=1-h+2^1+2^2+2^3+2^4+...+2^{h-3}+2^{h-2}+2^{h-1}$​

• $T(n)=2^0+2^1+2^2+2^3+2^4+...+2^{h-3}+2^{h-2}+2^{h-1}-h$$T{(n)}=2^0+2^1+2^2+2^3+2^4+...+2^{h-3}+2^{h-2}+2^{h-1}-h$

• $T(n)=2^h-1-h$$T{(n)}=2^{h}-1-h$

• $n=2^h-1$$n=2^{h}-1$ $h=lo{g}_2(n+1)$$h=log_2(n+1)$​

• $T(n)=n-lo{g}_2(n+1)\approx n$$T(n)=n-log_2(n+1)\approx n$​

直觉上我们可能会认为建堆的时间复杂度是 $O(n\ast logn)$$O(n*logn)$，因为对每个节点进行向下调整的时间复杂度是 $O(logn)$$O(logn)$。然而，由于深度较浅的节点较少，而深度较深的节点尽管多但每个节点的操作次数少，所以整个过程的平均成本实际上是线性的。

 

堆排序

在获取到一组数组数据并要对其堆排序时, 第一步就是先建堆. 然后再根据排升序或者降序的需求使用较优的方案

在首次面对堆排序的需求时, 直觉上首先想到的可能就是小堆排升序和大堆排降序, 表面上看起来更符合排序逻辑, 但是实际上操作起来不够简单和直接.

升序建小堆或降序建大堆为什么不行?

假设升序建小堆, 给定一个数组, 选出了最小的数据放在第0个位置, 然后要继续选出次小的数据,放到第一个位置, 那么问题来了, 要保持第0个位置不变, 就得把他排除出去, 然后把后面的看作一个堆, 一旦这样做后面堆成员之间的父子兄弟关系全乱套了, 只能重新建堆, 或者另开辟一个空间逐个移除堆顶元素放到新空间里, 无论哪种方法代价都太大了.

因此排升序建最大堆, 排降序建最小堆是比较优秀的方法, 下面说明实现思路:

升序排序:

1. 构建最大堆：从无序的输入数组中构建一个最大堆。确保了堆顶元素是当前堆中最大的元素。

2. 元素交换：将堆顶元素（最大元素）与堆中最后一个元素交换。

3. 堆大小调整：减少堆的大小（不再考虑数组中刚交换进来的元素)。

4. 堆的重新调整：对当前堆顶元素执行向下调整的操作，恢复最大堆的性质。新的堆顶元素就是次大的元素值

5. 重复步骤2-4：继续重复这个过程，每次都会将最大的元素移动到堆最后的位置(也就是插入到上一次循环中最大值的前面)，直到堆的大小减少到1，这时数组就成功排成升序

降序排序:

逻辑上和升序排序是一样的, 只不过切换成了小堆来执行

流程图示意:

C语言实现堆

Heap.h 函数声明

xxxxxxxxxx
38
1
#pragma once
2
#include <assert.h>
3
#include <stdio.h>
4
#include <stdbool.h>
5
#include <stdlib.h>
6

7
typedef int HeapDataType;
8

9
typedef struct Heap
10
{
11
    HeapDataType* arr;
12
    int size;
13
    int capacity;
14
}Heap;
15
bool BigHeap(HeapDataType parent, HeapDataType child);
16
bool SmallHeap(HeapDataType parent, HeapDataType child);
17
void HeapInit(Heap* php);
18
void HeapDestroy(Heap* php);
19
void HeapPush(Heap* php, HeapDataType x, bool(*bs)(HeapDataType, HeapDataType));
20

21
void AdjustUp(HeapDataType* arr, int child, bool(*bs)(HeapDataType, HeapDataType));
22

23
void Swap(HeapDataType* arr, HeapDataType parent, HeapDataType child);
24

25
//Pop删除首元素
26
void HeapPop(Heap* php, bool(*bs)(HeapDataType, HeapDataType));
27
//向下调整
28
void AdjustDown(HeapDataType* arr, int parent, int size, bool(*bs)(HeapDataType, HeapDataType));
29

30
bool HeapIsEmpty(Heap*php);
31

32
//向上建堆 然后堆排序
33
void HeapSort(HeapDataType* arr, int size, bool(*bs)(HeapDataType, HeapDataType));
34

35
//向下建堆,然后堆排序
36
void HeapSort2(HeapDataType* arr, int size, bool(*bs)(HeapDataType, HeapDataType));
37

38
void printArr(int* arr, int sz);

Heap.c 函数定义

包含头文件

xxxxxxxxxx
2
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "Heap.h" //包含头文件

定义这两个函数用来作为函数指针传递给其他函数, 主要作用是根据需要建立大堆或小堆, 在C语言中只能使用这种比较挫的方法, 以后写到C++会用一些比较高级和好玩的方法

xxxxxxxxxx
8
1
bool BigHeap(HeapDataType x, HeapDataType y)
2
{
3
    return x < y;
4
}
5
bool SmallHeap(HeapDataType x, HeapDataType y)
6
{
7
    return x > y;
8
}

初始化堆

xxxxxxxxxx
7
1
void HeapInit(Heap* php)
2
{
3
    assert(php);
4
    php->size = 0;
5
    php->capacity = 0;
6
    php->arr = NULL;
7
}

释放堆

xxxxxxxxxx
8
1
void HeapDestroy(Heap* php)
2
{
3
    assert(php);
4
    free(php->arr);
5
    php->arr = NULL;
6
    php->capacity = 0;
7
    php->size = 0;
8
}

向上调整方法

在定义该函数时, 我没有选择直接传结构体指针进去, 而是传了一个数组元素的指针, 其目的是为了让该函数不仅能作用于定义的结构体, 并且也支持直接对数组调整

xxxxxxxxxx
24
1
void AdjustUp(HeapDataType* arr, int child, bool(*bs)(HeapDataType, HeapDataType))
2
{
3
    assert(arr);
4
    int parent = (child -1) / 2;
5
    while (child>0)
6
    {
7
        if (bs(arr[parent], arr[child]))
8
        {
9
            Swap(arr, parent, child);
10
        }
11
        else
12
        {
13
            break;
14
        }
15
        child = parent;
16
        parent = (child - 1) / 2;
17
    }
18
}
19
void Swap(HeapDataType* arr, HeapDataType parent, HeapDataType child)
20
{
21
    HeapDataType tmp = arr[parent];
22
    arr[parent] = arr[child];
23
    arr[child] = tmp;
24
}

插入堆

元素插入到最后一个位置, 然后再向上调整保持堆性质

xxxxxxxxxx
19
1
void HeapPush(Heap*php, HeapDataType x, bool(*bs)(HeapDataType, HeapDataType))
2
{
3
    assert(php);
4
    if (php->size == php->capacity)
5
    {
6
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
7
        HeapDataType* tmp = (HeapDataType*)realloc(php->arr, sizeof(HeapDataType)*newcapacity);
8
        if (tmp == NULL)
9
        {
10
            perror("malloc fail");
11
            return;
12
        }
13
        php->arr = tmp;
14
        php->capacity = newcapacity;
15
    }
16
    php->arr[php->size++] = x;
17

18
    AdjustUp(php->arr, php->size-1, bs);
19
}

移除堆元素(堆顶元素)

xxxxxxxxxx
8
1
void HeapPop(Heap* php, bool(*bs)(HeapDataType, HeapDataType))
2
{
3
    assert(php);
4
    assert(!HeapIsEmpty(php));
5
    Swap(php->arr, 0, php->size-1);
6
    AdjustDown(php->arr, 0, php->size-1, bs);//size得减1,因为被移除的元素不参与向下调整计算
7
    php->size--;
8
}

向下调整

基本没什么可说, 都是换汤不换药, 唯一需要注意的一点是增加一条判断当前循环是否存在右子树的情况

xxxxxxxxxx
16
1
void AdjustDown(HeapDataType* arr, int parent, int size, bool(*bs)(HeapDataType, HeapDataType))
2
{
3
    assert(arr);
4
    int child = parent * 2 + 1;
5
    while (child <size)
6
    {
7
        if (child + 1 < size && bs(arr[child], arr[child + 1]))
8
            child++;
9
        if (bs(arr[parent], arr[child]))
10
            Swap(arr, parent, child);
11
        else
12
            break;
13
        parent = child;
14
        child = parent * 2 + 1;
15
    }
16
}

判空

xxxxxxxxxx
5
1
bool HeapIsEmpty(Heap* php)
2
{
3
    assert(php);
4
    return php->size == 0;
5
}

堆排序

xxxxxxxxxx
37
1
void HeapSort(HeapDataType* arr, int size, bool(*bs)(HeapDataType, HeapDataType))
2
{
3
    assert(arr);
4
    //先建堆
5
    for (int i = 0; i < size; i++)
6
    {
7
        //AdjustDown(arr, 0, i, bs);从头向下调整是不可行的,因为拿到的初始数组不满足堆性质
8
        AdjustUp(arr, i, bs);//从前到后遍历向上调整建堆, 方法可行, 但是效率不高
9
    }
10

11
 //开始堆排序
12
    int end = size;
13
    while (end--)
14
    {
15
        Swap(arr, 0, end);
16
        AdjustDown(arr, 0, end, bs);
17
    }
18
}
19

20
void HeapSort2(HeapDataType* arr, int size, bool(*bs)(HeapDataType, HeapDataType))
21
{
22
    assert(arr);
23
    //先建堆
24
    //从尾开始向下调整, 直接从最后一个父节点开始向前遍历, 建堆时间复杂度O(N)
25
    for (int i = (size - 2) / 2; i >= 0; i--)
26
    {
27
        AdjustDown(arr, i, size, bs);
28
    }
29

30
 //开始堆排序
31
    int end = size;
32
    while (end--)
33
    {
34
        Swap(arr, 0, end);
35
        AdjustDown(arr, 0, end, bs);
36
    }
37
}

xxxxxxxxxx
8
1
void printArr(int* arr, int sz)
2
{
3
    for (int i = 0; i < sz; i++)
4
    {
5
        printf("%d ", arr[i]);
6
    }
7
    printf("\n");
8
}

test.c测试

xxxxxxxxxx
56
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "Heap.h"
3

4
void test()
5
{
6
    bool(*bs)(HeapDataType, HeapDataType) = BigHeap;
7
    bs = SmallHeap;
8
    Heap hp;
9
    HeapInit(&hp);
10

11
    HeapDataType arr[] = { 3,7,2,5,9,1,6,4,3,8 };
12
    int sz = sizeof(arr) / sizeof(arr[0]);
13
    for (int i = 0;i < sz;i++)
14
    {
15
        HeapPush(&hp, arr[i], bs);
16
    }
17
    printArr(hp.arr, hp.size);
18
    HeapPop(&hp, bs);
19
    HeapPop(&hp, bs);
20
    HeapPop(&hp, bs);
21
    printArr(hp.arr, hp.size);
22

23
    HeapDestroy(&hp);
24

25
}
26

27
test2()
28
{
29
    bool(*bs)(HeapDataType, HeapDataType) = BigHeap;
30
    bs = SmallHeap;
31
    //降序
32
    HeapDataType arr[] = { 3,7,2,5,9,1,6,4,3,8 };
33
    int sz = sizeof(arr) / sizeof(arr[0]);
34
    //直接将数组视作二叉堆进行堆排序
35
    HeapSort(arr, sz, bs);
36
    printArr(arr, sz);
37
    HeapDestroy(&hp);
38
}
39
void test3()
40
{
41
    bool(*bs)(HeapDataType, HeapDataType) = BigHeap;//升序
42
    //bs = SmallHeap;
43
    HeapDataType arr[] = { 3,7,2,5,9,1,6,4,3,8 };
44
    int sz = sizeof(arr) / sizeof(arr[0]);
45
    //直接将数组视作二叉堆进行堆排序
46
    HeapSort2(arr, sz, bs);
47
    printArr(arr, sz);
48
    HeapDestroy(&hp);
49
}
50
int main()
51
{
52
    test();
53
    test2();
54
    test3();
55
    return 0;
56
}

就先写到这里吧, 祝大家龙年大吉