关注码农话题
做一个实实在在的内行人

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

key(α) ≥ key(β)

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

For Input → 35 33 42 10 14 19 27 44 26 31
  • 最小堆 − 其中根节点的值小于或等于任一其子点。

Max Heap Example

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

Max Heap Example

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

最大堆构造算法

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

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

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

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

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

Max Heap Animated Example

最大堆删除算法

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

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

Max Heap Deletion Animated Example

 


入职你的梦想 VS 变现你的技术

IT面试宝典码农市场