sift down右孩子比左孩子大的问题

Question

波波老师您好，若第二层右侧节点值为42的话，sift down按照孩子节点最大的来选择，是否会导致第三层16的节点没有右孩子，而22的节点有左孩子，这样中间就有一个空的了

Answer 1

笨蛋某某某 2019-09-24 16:33:46

节点15在与根节点交换位置后 其右子树中没有增加新的节点 所以不会破坏完全二叉树这个前提 谢谢老师指导

Answer 2

liuyubobobo 2019-06-24 02:20:38

不会。

我要没理解错，你的意思是如果测试用例是这样：

           52
         /    \
      41       42
    /    \    /  \
  28     16  22   13
 /  \   /
19  17 15

取出最大元素，52出堆。15放到堆顶。变成这样：

           15
         /    \
      41       42
    /    \    /  \
  28     16  22   13
 /  \   
19  17

对15开始下沉，首先，42比41大，向42下沉：

           42
         /    \
      41       15
    /    \    /  \
  28     16  22   13
 /  \   
19  17

继续对15下沉，22比15大，下沉：

           42
         /    \
      41       22
    /    \    /  \
  28     16  15   13
 /  \   
19  17

15已经是叶子节点，下沉结束。

用课程的代码，用你觉得有问题的测试用例，实际测试一下，看看是不是会出现你所想象的问题？如果没有出现，仔细思考一下为什么，自己的思考哪里有问题，哪里想错了或者有遗漏？

进步就发生在这个过程中哦：）

继续加油！：）

• 提问者 慕先生2077633 #1

  懂了懂了，感谢老师

• 那月真美 #2

  假如测试用例是这样呢？
         52
           /    \
        41       42
      /    \    /  \
    28     16  22   13
   /  \   /   \
  19  17 15 11
  取出最大元素，然后下沉，会不会破坏平衡？

• liuyubobobo 回复 那月真美 #3

  不会。模拟一遍试试看？

点开查看后面3条评论