将值插入二进制堆（构建时）背后的逻辑是什么？

Question

我下周有期中考试，我很难画出二叉堆。最小二叉堆的不变量是：存储在父节点的项的值总是小于（大于）存储在其子节点的项的值。我不明白的部分是当我向堆中插入值时，我怎么知道是向左还是向右？我真的很想看到一步一步的解决方案，因为我只是不明白我怎么知道是向左走还是向右走。

假设我有以下值：5、8、13、15、1、2、12、4 它会像

一样开始

  5 then I insert 8
 / \ 
8? 13? is this going in the right direction?

我知道二叉搜索树的不变量是左<父<右，但我真的很困惑如何确定是向左还是向右。

Answer 1

你选择的方向保证底层树是完全二叉树：

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

让我们将涓流方法应用到一个例子中。假设您要向堆中添加一个新元素 e。如果堆看起来像这样：

     5                                    5
   /   \                                /   \    
  6     9    add as right-child-->     6     9     then trickle-up
 / \   / \     to complete the        / \   / \
7                    tree            7   e

然后将新元素添加为 6 的右子元素并逐级递增（即重复将新元素与其父元素交换，直到恢复堆不变量）。

另一方面，如果堆看起来像这样：

     5                                   5
   /   \                               /   \    
  6     9   add as left-child -->     6     9     then trickle-up
 / \   / \   to complete the         / \   / \
7  10              tree             7  10 e

然后将最新的元素添加为 9 的左子元素并逐渐增加。

对于您的示例，添加顺序是 5、8、13、15、1、2、12、4。以下代码片段显示了 insert/trickle-up 分步操作：

    Add 5:

     5

    No change due to trickle, So add 8:
     
       5
      /
     8
     
    No change due to trickle-up. So, add 13:

          5
      / \
     8  13
     
    No change due to trickle-up. So, add 15:
         5
        / \
       8  13
      / 
     15

    No change due to trickle-up. So, add 1:
     
         5
        / \
       8  13
      / \
     15  1
     
    Then trickle-up:
     
         1
        / \
       5  13
      / \
     15  8

    Next, add 2:
     
           1
        /     \
       5      13
      / \    /
     15  8  2
     
    Then trickle-up
     
           1
        /     \
       5       2
      / \     /
     15  8   13
     
    Next, add 12:

           1
        /     \
       5       2
      / \     / \
     15  8   13 12
     
    No change due to trickle-up. So, add 4:

                1
          /     \
         5       2
        / \     / \
       15  8   13 12
      /
     4
     
    Then trickle-up:
     
             1
          /     \
         4       2
        / \     / \
       5  8   13 12
      /
     15

将值插入二进制堆（构建时）背后的逻辑是什么？

What is the logic behind inserting values into binary heaps (when build one)?

heap

tree

binary-heap