C++ 数据结构 堆

迪士尼在逃驸马

参考文献：

数据结构--堆（带图详解）_Owen_Xp的博客-CSDN博客_数据结构堆
简书 数据结构：堆
堆定义

如果有一个数据的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。如果满足：

• 每个节点的值总是 <= 其父节点的值，那么这就是一个大根堆；
  
• 每个节点的值总是 >= 其父节点的值，那么这就是一个小根堆。
  

如图所示：

堆 其实就是 一个完全二叉树 其中堆又分为 小堆 和 大堆
小堆 就是 根节点是所有数据中最小的
大堆 就是 根节点是所有数据中最大的

堆属性

堆分为两种：大根堆和小根堆，两者的差别在于节点的排序方式。

• 在大根堆中，父节点的值比每一个子节点的值都要大。
  
• 在小根堆中，父节点的值比每一个子节点的值都要小。
  

这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。

• 大根堆总是将其中的最大值存放在树的根节点
  
• 小根堆根节点中的元素总是树中的最小值
  

堆属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到“最重要”的元素。
堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。
例如，在一个大根堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。--唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

二叉树的基本性质

参考文献：【数据结构】 实现 堆 结构 ---超细致解析

• 如果根节点的层数为1，则一个非空二叉树的第 i 层上最多有2^(i-1)个节点
  
• 若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h - 1
  
• 对于任何一棵二叉树，如果度为0的节点个数是n0，度为2的分支节点个数为n2，则有n0=n2+1
  
• 如果说根节点的层数为1，那么具有那个节点的满二叉树的深度 h=log2(n+1);
  

完全二叉树的顺序存储

二叉树一般有两种存储结构：

• 一个顺序结构
  
• 一个链式结构
  

顺序结构存储就是使用数组来存储，一般只适合表示完全二叉树，因为如果不是完全二叉树，存储时会有空间的浪费。由于堆实际上是一棵完全二叉树，所以堆可以使用数组来存储。
顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。


父节点和子节点的序号

参考文献：【数据结构】【堆】堆的建立、插入和删除_西西敏的博客-CSDN博客_堆的插入
下图是一个堆常用的编号方式示意图：根节点编号为0，根节点的左子节点编号为1、右子节点编号为2，再往下是3、4、5、6……即按照从上往下、从左往右的顺序编号。


在数组中，就按照如上所述的下标进行保存，如上图保存为数组就是{10, 20, 15, 25, 50, 30, 40, 35, 45}。
在这样一个数组中：
下标为i的节点的父节点的下标就是： (i - 1) / 2（除法向下取整）；
下标为i的节点的左子节点的下标是2 * i + 1，
下标为i的节点的右子节点的下标是2 * i + 2。
示例：
第3个元素(25)的左子节点是第（2 * 3 + 1 = 7）个元素(35)，
而它的右子节点是第（2 * 3 + 2 = 8）个元素(45)。堆的插入

首先，在堆的第一个空白位置处插入这个新元素，然后递归调用上述的shiftUp()操作，直到它的父节点比它大（最大堆）或小（最小堆）。
示例：
我们通过一个插入例子来看看插入操作的细节。我们将数字16插入到这个堆中：


第一步是将新的元素插入到堆的第一个空白位置处。则堆变成：


不幸运的是，现在堆不满足堆的属性，因为 2 在 16 的上面，我们需要将大的数字在上面（这是一个最大堆），为了恢复堆属性，我们需要交换16和2。
现在还没有完成，因为 10 也比 16 小。我们继续交换我们的插入元素和它的父节点，直到它的父节点比它大或者我们到达树的顶部。这就是所谓的shiftUp()，每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。
最后我们得到的堆：


现在每一个父节点都比它的子节点大，满足了最大堆的属性。

堆是不支持什么在 中间 插入删除数据的
这种操作是顺序表中使用的 但我们的堆虽然是使用的数组的结构 但那只是物理上面的 逻辑上面可不是那样的哦

堆的删除

为了将这个节点删除后的空位填补上，首先要将本堆中最后一个元素的值（假设为value）移动到此位置，然后在被删位置处，用此位置当前的值value和此处的父节点、子节点去比较，如果它与父节点的关系破坏了最大（小）堆，则递归调用shiftUp()来修复；如果它与子节点的关系破坏了最大（小）堆，则递归调用shiftDown()来修复。
示例：
我们将这个树中的 (10) 删除：


现在顶部有一个空的节点，怎么处理？


当插入节点的时候，我们将新的值返给数组的尾部。
现在我们来做相反的事情：我们取出数组中的最后一个元素，将它放到树的顶部，然后再修复堆属性。
现在被删除位置处的元素值为1，由于它没有父节点，所以我们只把它与子节点进行比较，看是否违反了最大堆的属性：现在有两个数字（ 7 和 2）可用于交换。我们选择这两者中的较大者称为最大值放在树的顶部，所以交换 7 和 1，现在树变成了：


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


如上，就完成了堆的删除操作
堆的建立

堆的插入和删除操作都不是最难的，最难的是堆的建立。这里我们以最大堆为例，讲讲如何由一个无序数组，建立一个最大堆。
建立最大(小)堆的原理是，只要保证了某节点的左右子树是最大(小)堆，那么只要对此节点不断做shifDown()操作，那么最终就能把以此节点为根节点的树变成最大(小)堆。也就是说，把以某节点为根节点的子树，调整成一个最大(小)堆。
那么，只要在一棵二叉树中，从最后一个非叶子节点开始，从下往上地对每个节点都做此操作，就能把整棵树调整成一个最大(小)堆。
我们边针对上边数组操作如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。


堆排序