如何创建堆？

Question

假设我有一个像下面这样的堆：

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

现在，我想将另一个项目55插入到这个堆中。

如何操作？

选项1。

         77
        /  \
       /    \
      55    60
     / \    / \
    50 30  44 55
   /
  22

选项2。

     77
    /  \
   /    \
  55    60
 / \    / \
22 50  44 55
     \
     30

Option 3.

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  55 55
      /
     44

哪一个是正确的步骤？为什么？请解释。

请解释哪一个是正确的步骤以及为什么。

- user366312

Answer 1

选项1是正确的。因为我们从最左边的节点开始添加子节点，如果父节点比新添加的子节点小，那么我们就替换它们。这样一直进行下去，直到子节点得到了大于它的值的父节点。

您的初始树如下：

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

现在按照最左边的规则添加55。

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55
/
55

但是您可以看到22比55要小，所以进行了替换。

       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22 

现在55已经成为50的子级，仍然低于55，因此也要替换它们。

       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

现在无法再排序，因为77大于55... 所以你的选项1是正确的。在这里，您可以详细了解堆排序示例。此链接说明堆是一种满足堆属性的专用基于树的数据结构：如果B是A的子节点，则key（A）≥key（B）。这意味着具有最大键的元素始终位于根节点，因此这样的堆有时称为max-heap。（或者，如果比较反转，则最小元素始终位于根节点，从而得到min-heap。）在堆中，每个节点的子节点数量没有限制，尽管在实践中，每个节点最多有两个子节点。祝好运。

- Syeda

Answer 2

第一种选项，按照定义，二叉堆的形状是一个完全二叉树。而其他两种选项不是完全二叉树。 详情请参见 http://en.wikipedia.org/wiki/Binary_heap

- MK.

---

是的。但除了方便之外，我想不出任何特定的原因需要将任何特定的实现限制在严格的二叉堆中。话虽如此，目前我也想不出任何非常有说服力的理由来使用其他东西。 - jpm

如果它是完整的，你可以将其实现为一个数组。否则，你必须使用完整的树实现。此外，完整的树是一棵平衡树。 - MK.

你也可以将不完整的堆放入数组中，但这样做有点浪费。 - jpm

@jpm 是的，当我写下那个数组注释时，我也不知道自己在想什么。该去睡觉了。 - MK.

Answer 3

正确选项是1。

为什么呢？

记住，堆的一个属性是成为完全二叉树，即除了最后一层可能不完全填充外，所有层都是完全填充的，并且所有节点尽可能靠左...维基百科？

在选项2和3中，元素没有插入到尽可能靠左的位置，因此完全二叉树的属性被破坏了。

关于元素的最终位置，是通过将插入的元素（子节点）与其直接祖先（父节点）交换，而当子节点小于父节点时进行交换。

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55


       77
      /  \
     /    \
    50    60
   / \    / \
  22 30  44 55
 /
55


       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22


       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

- rendon