请问波波老师这个shift Down的问题

Question

shift down这个函数向子节点依次进行了比较，有没有这种情况，如果堆的最后一个值比替换的节点两个子节点都要大，并且比这个替换节点的父节点也大，那么这个shift Down这个函数执行以后会不会打破最大堆的数据结构？

Answer 1

liuyubobobo 2020-02-05 03:00:10

不会出现这种情况。

以课程介绍的最大堆为例，删除掉堆顶元素，将最后一个元素放到堆顶，进行 sift down，此时，整个树，除了堆顶的元素，一定依然满足最大堆的性质。即除了堆顶元素，所有的父亲节点一定比孩子节点大。

最后一个值也不可能比替换的节点两个子节点都要大，否则原来就不是最大堆。

你也可以尝试一下构造一下你说的情况，看是否会存在？

继续加油！：）