数据结构&算法 堆

• 

  堆数据结构

  堆是平衡二叉树数据结构的一种特例，其中根节点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，直到堆属性保持。