如何创建堆？

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是正确的.. 因为我们开始从最左边的节点添加子节点,如果父节点低于新添加的子节点,则替换它们.并且这样下去将继续,直到孩子得到父母的价值大于它.

你的初始树是

     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的子节点,则键(A)≥键(B).这意味着具有最大键的元素始终位于根节点中,因此这样的堆有时称为最大堆.(或者,如果比较相反,最小元素总是在根节点中,这会产生最小堆.)对于每个节点在堆中有多少个子节点没有限制,尽管实际上每个节点都有最多两个.

祝好运