2021/6/15 堆

备注：

1. 本文中[ ]表示向下取整。
2. 度为：二叉树中连接节点和节点的线就是度。
3. 叶子节点

堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

小根堆的概念：

堆是非线性数据结构，相当于一维数组，有两个直接后继。

堆的性质：

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

补充知识点：

什么是完全二叉树：

概念: 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

完全二叉树的性质

1. 具有n个结点的完全二叉树的深度

（注：[ ]表示向下取整）

1. 如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有:
   • 如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点[i/2].
   • 如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i;
   • 如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1.

完全二叉树的特点

1. 叶子结点只可能在最大两层出现。（不是的话得补全）
2. 右子树不可以单独存在。
3. 度为1的结点只有0或1个

补充知识：

什么是非完全二叉树?

与完全二叉树的区别就是是否可以存在右子树。

非完全二叉树可以出现单独的右子树，完全二叉树不可以出现单独的右子树。

什么是满二叉树：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

定义：

从图形形态上看，满二叉树外观上是一个三角形。

从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。

因此由等比数列的公式，满二叉树满足如下性质。

1. 一个层数为k 的满二叉树总结点数为：因此满二叉树满二叉树满2 叉树节点数的结点数一定是奇数个。

2、第i层上的结点数为：

3、一个层数为k的满二叉树的叶子结点个数（也就是最后一层）：