logo图片
数据结构与算法

堆数据结构

堆是平衡二叉树数据结构的一种特殊情况,其中根节点键与其子节点进行比较并进行相应排列。如果 α 有子节点 β 那么-
key(α) ≥ key(β)
由于 parent 的值大于 child 的值,因此该属性生成 Max Heap。基于这个标准,堆可以有两种类型-
for Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap-根节点的值小于或等于其任一子节点。
最大堆示例
Max-Heap-根节点的值大于或等于其任一子节点。
最大堆示例
两棵树都是使用相同的输入和到达顺序构建的。

最大堆构造算法

我们将使用相同的示例来演示如何创建最大堆。创建最小堆的过程类似,但我们使用最小值而不是最大值。
我们将通过一次插入一个元素来推导最大堆的算法。在任何时候,堆都必须保持其属性。在插入时,我们还假设我们正在向已经堆积的树中插入一个节点。
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4if value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
注意-在最小堆构造算法中,我们期望父节点的值小于子节点的值。
让我们通过一个动画插图来了解 Max Heap 的构造。我们考虑之前使用的相同输入样本。
最大堆动画示例

最大堆删除算法

让我们推导出一个从最大堆中删除的算法。最大(或最小)堆中的删除总是发生在根处以删除最大(或最小)值。
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4if value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
最大堆删除动画示例
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4