数据结构&算法 堆
-
堆数据结构
堆是平衡二叉树数据结构的一种特例,其中根节点key与其子节点进行比较并进行相应安排。如果α具有子节点β,则-键(α)≥ 键(β)当parent的值大于child的值时,此属性将生成Max Heap。基于此标准,堆可以为两种类型-- 最大堆
- 最小堆
For Input → 35 33 42 10 14 19 27 44 26 31
最小堆 - 根节点的值小于或等于其子节点中的一个。最大堆 - 根节点的值大于或等于其子节点中的一个。两种树都是使用相同的输入和到达顺序构造的。 -
最大堆构造算法
我们将使用相同的示例来演示如何创建最大堆。创建最小堆的过程类似,但是我们使用最小值而不是最大值。我们将通过一次插入一个元素来导出最大堆的算法。在任何时候,堆都必须维护其属性。在插入时,我们还假设我们正在已堆化的树中插入节点。Step 1 − 在堆的末端创建一个新节点。 Step 2 − 为节点分配新值。 Step 3 − 将子节点的值与其父节点进行比较。 Step 4 − 如果父值小于子值,则交换它们。 Step 5 − 重复步骤3和4,直到堆属性保持。
注 -在最小堆构造算法中,我们期望父节点的值小于子节点的值。让我们通过动画插图了解Max Heap的构造。我们考虑与之前使用的输入样本相同的样本。 -
最大堆删除算法
让我们导出一种从最大堆中删除的算法。最大(或最小)堆中的删除始终发生在根部,以删除最大(或最小)值。Step 1 − 删除根节点。 Step 2 − 将最后一层的最后一个元素移动到根。 Step 3 − 将子节点的值与其父节点进行比较。 Step 4 − 如果父值小于子值,则交换它们。 Step 5 − 重复步骤3和4,直到堆属性保持。