data-structures - 如何创建堆？

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

选项 3。

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

哪个是正确的步骤？和 Why ?请解释。

Answer 1

选项 1 是正确的..
因为我们从最左边的节点开始添加子节点，如果父节点低于新添加的子节点，我们将替换它们。就像这样会一直持续下去，直到 child 的 parent 拥有比它更大的值(value)。

你的初始树是

     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的 child ，还低于55，所以也要换掉。

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

现在不能排序了，因为 77 大于 55 ...
所以你的选项 1 是正确的。

here您可以详细查看堆排序示例..
This link states
堆是一种特殊的基于树的数据结构，它满足堆属性:如果 B 是 A 的子节点，则 key(A) ≥ key(B)。这意味着具有最大键的元素总是在根节点中，因此这种堆有时称为最大堆。 (或者，如果反向比较，最小的元素总是在根节点中，这导致了一个最小堆。)对于每个节点在一个堆中有多少个子节点没有限制，尽管实际上每个节点都有最多两个。

祝你好运