数据结构&算法 堆

  • 堆数据结构

    堆是平衡二叉树数据结构的一种特例,其中根节点key与其子节点进行比较并进行相应安排。如果α具有子节点β,则-键(α)≥ 键(β)
    当parent的值大于child的值时,此属性将生成Max Heap。基于此标准,堆可以为两种类型-
    • 最大堆
    • 最小堆
    For Input → 35 33 42 10 14 19 27 44 26 31
    最小堆 - 根节点的值小于或等于其子节点中的一个。
    tree
    最大堆 - 根节点的值大于或等于其子节点中的一个。
    tree
    两种树都是使用相同的输入和到达顺序构造的。
  • 最大堆构造算法

    我们将使用相同的示例来演示如何创建最大堆。创建最小堆的过程类似,但是我们使用最小值而不是最大值。我们将通过一次插入一个元素来导出最大堆的算法。在任何时候,堆都必须维护其属性。在插入时,我们还假设我们正在已堆化的树中插入节点。
    
    Step 1 − 在堆的末端创建一个新节点。
    Step 2 − 为节点分配新值。
    Step 3 − 将子节点的值与其父节点进行比较。
    Step 4 − 如果父值小于子值,则交换它们。
    Step 5 − 重复步骤3和4,直到堆属性保持。
    
    注 -在最小堆构造算法中,我们期望父节点的值小于子节点的值。让我们通过动画插图了解Max Heap的构造。我们考虑与之前使用的输入样本相同的样本。
    tree
  • 最大堆删除算法

    让我们导出一种从最大堆中删除的算法。最大(或最小)堆中的删除始终发生在根部,以删除最大(或最小)值。
    
    Step 1 − 删除根节点。
    Step 2 − 将最后一层的最后一个元素移动到根。
    Step 3 − 将子节点的值与其父节点进行比较。
    Step 4 − 如果父值小于子值,则交换它们。
    Step 5 − 重复步骤3和4,直到堆属性保持。
    
    tree