堆的基本操作

堆的基本操作

堆的主要操作是插入和删除最小(最大)元素(元素值本身为优先级键值，小元素享有高优先级)。在插入或者删除操作之后，我们必须保持该实现应有的性质:

1. 完全二叉树
2. 每个节点值都小于或等于它的子节点。

以下的所有操作都以以最小堆为例，最大堆是同样的道理。

1. 堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2∗i+1和2∗i+2。如第0个结点左右子结点下标分别为1和2。

2、堆的建立

简单说就下面几个要点（以大顶堆为例）：

• 首先根据序列构建一个完全二叉树
• 在完全二叉树的基础上，从最后一个非叶结点开始调整：比较三个元素的大小–自己，它的左孩子，右孩子。分为三种情况:
  • 自己最大，不用调整
  • 左孩子最大，交换该非叶结点与其左孩子的值，并考察以左孩子为根的子树是否满足大顶堆的要求，不满足递归向下处理
  • 右孩子最大，交换该非叶结点与其右孩子的值，并考察以右孩子为根的子树是否满足大顶堆的要求，不满足递归向下处理
  • 就这些基本要求，就可以解决这一类的手工计算问题。举个例子：

比如：一组记录(5,11,7,2,3,17)利用大顶堆排序方法建立初始堆为？

分析：首先建立完全二叉树。

再从最后一个非叶结点开始调整。
第一次交换7，17的位置。

11不用调整。
最后调整根结点。

此时把5换下去后，以5为根的子树不满足大顶堆的要求，因此再调整。

即最终的初始堆是：17，11，7，2，3，5.

3. 插入

在插入操作的时候，将新插入的节点放在完全二叉树最后的位置，再和父节点比较。如果new节点比父节点小，那么交换两者。交换之后，继续和新的父节点比较…… 直到new节点不比父节点小，或者new节点成为根节点。这样得到的树，就恢复了堆的性质。

4. 删除

删除操作只能删除根节点。根节点删除后，我们会有两个子树，我们需要基于它们重构堆。 让最后一个节点last成为新的节点，从而构成一个新的二叉树。再将last节点不断的和子节点比较。如果last节点比两个子节点中小的那一个大，则和该子节点交换。直到last节点不大于任一子节点都小，或者last节点成为叶节点。

本文参考文章：
https://blog.csdn.net/john_xyz/article/details/79331465
https://blog.csdn.net/u011240016/article/details/53428489