二叉堆应用

Question

我刚刚完成了有关二叉堆概念的练习。然而，我没有解决这个问题的方法，但我在这个练习中找到了答案。有人可以验证我得到的解决方案是否正确吗？

提前致谢！

这是我得到的答案： x F G M K T S Z U Q

Answer 1

给定的二叉堆是 Max Heap ，其中 Heap Size 是 8

            F
         /     \
      K          M
    /   \      /   \
   Q     T    S     Z
  /
 U

要插入字母 G ，我们遵循 MAX-HEAP-INSERT 算法。

第 1 步 - 将堆大小增加一，并在末尾添加 -∞，现在我们的二进制堆看起来像这样..

            F
         /     \
      K          M
    /   \      /   \
   Q     T    S     Z
  / \
 U   -∞

第 2 步 - 现在使用 HEAP INCREASE KEY 算法将 -∞ 的大小增加到 G

            F
         /     \
      K          M
    /   \      /   \
   Q     T    S     Z
  / \
 U   G

G 可能违反堆条件，向上到达根并与父级交换 G，直到找到有效的堆。

用Q交换G

            F
         /     \
      K          M
    /   \      /   \
   G     T    S     Z
  / \
 U   Q

用K交换G

            F
         /     \
      G          M
    /   \      /   \
   K     T    S     Z
  / \
 U   Q

生成的堆是有效的堆，不再需要交换。

让我们把这个堆写成数组的形式 -

x F G M K T S Z U Q