siftDown函数问题

问题描述：

bobo老师,为什么 j 在 +1(变为rightChild(k)) 后是 leftChild 和 rightChild 中的最大值? 不是等于rightChild吗？

相关代码：

 private void siftDown(int k){
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k); //j+1是右节点,不越界,说明存在
            if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)
                j ++; // j = rightChild(k);
            //data[j] 是 leftChild 和 rightChild 中的最大值

白熊233333 2021-11-25

源自：堆，优先队列和堆排序 1-4 从堆中取出元素和Sift Down

收起

2回答

假蛙工程师 2021-12-15 16:11:58

这么说可能方便理解。

int j;

这里j的语义是索引K（表示的节点）的左孩子和右孩子中值较大的（节点）的索引。

初始时，假设左孩子的值较大，因此 j = leftchild(k);

如果有右孩子且右孩子的值比左孩子的值大，那么j = rightchild(k); 效果和j= j + 1 (相当于j ++）一样

收起回答

liuyubobobo 2021-11-25 12:01:51

j ++ 是有条件的：

if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)

这个条件的意思是： j + 1 没有越界且 data[j + 1] > data[j]，此时，才 j ++，

也就是右边大于左边，才 j ++。所以走完这个 if 以后，data[j] 里是 leftChild 和 rightChild 中的最大值

继续加油！：）

收起回答

提问者白熊233333 #1

bobo老师, 我的意思是满足条件后 j ++(j +1)后, 这时的 j 是大于还是等于 rightChild?

2021-11-25 12:18:45
提问者白熊233333 #2

j+1后不是应该等于 rightChild吗？

2021-11-25 12:21:27
liuyubobobo 回复提问者白熊233333 #3

我觉得我没有理解你的问题。j ++ 以后 j 指向当前 while 循环中 k 的右节点的索引

2021-11-25 12:24:09