为什么Heaplify 过程要从第一个非叶子节点开始往下shiftdown? 可以从根节点开始往下shiftdowndown 么？

来源：4-5 基础堆排序和Heapify

缱绻091

2020-01-30

如题
为什么Heaplify 过程要从第一个非叶子节点开始往下shiftdown? 可以从根节点开始往下shiftdowndown 么？谢谢·！

写回答

1回答

liuyubobobo

2020-01-30

已采纳

不可以。因为必须保证子树是堆，才能得到正确的结果。

以最小堆为例，比如初始是这样的：

     9
   /   \
  7     8
 / \   / \
3   4 1   2

如果从根节点开始开始，下一步要具体怎么做？根据我们的下沉逻辑，先和 7 换（7 比 8 小），再和 3 换（3 比 4 小），结果是这样的：

     7
   /   \
  3     8
 / \   / \
9   4 1   2

显然是不正确的。

但如果从第一个飞叶子节点开始反向处理，则没有这个问题。手动试一试这个例子，再仔细体会一下为什么反向处理没有这个问题？

继续加油！：）

缱绻091

非常感谢老师详尽的回复！

2020-01-31

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 3

回答 2

回答 1

回答 4