堆

堆是平衡二叉树数据结构，其中根节点键与它的子相比并设置相应在一种特殊情况。如果α有子节点β那么 -

key(α) ≥ key(β)

作为父的值大于这个子，这个属性会产生最大堆。基于该标准堆可以有两种类型 -

For Input → 35 33 42 10 14 19 27 44 26 31

• 最小堆 − 其中根节点的值小于或等于任一其子点。

• 最大堆 − 其中根节点的值大于或等于任一其子节点。

两个树都使用相同的输入及到达顺序构成。

最大堆构造算法

我们将用同样的例子来说明如何创建最大堆。程序创建最大堆与最小堆是类似，但使用最小值代替最大值。

我们将通过一次插入一个元素以导出最大堆算法。在任何时间点，堆必须保持其性能。 当在插入时，假设插入在堆字段在树中的节点。

Step 1 − 在堆的末尾创建新节点
Step 2 − 分配节点的新值
Step 3 − 比较其父与这个孩子节点的值
Step 4 − 如果父值小于子，那么交换它们
Step 5 − 重复步骤3和4，直到堆属性保存

注 − 在最小堆构造算法，预计父节点的值要小于子节点。

我们先看一张卡通插图来了解最大堆构建。拿我们之前用的相同输入样本。

最大堆删除算法

让我们推导一个算法的最大堆删除。删除最大（小）堆总是发生在根部去除最大（或最小）值。

Step 1 − 删除
Step 2 − 分配节点的新值
Step 3 − 比较其父与这个孩子节点的值
Step 4 − 如果父值小于子，那么交换它们
Step 5 − 重复步骤3和4，直到堆属性保存