1回答

liuyubobobo

2017-07-13

非常好的 问题。对于这类问题，可以通过简单的分析代码得出结论。我们来看我们在第3节实现的代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/04-Heap/Course%20Code%20(C%2B%2B)/03-Shift-Up/main.cpp

向堆中插入一个元素使用insert方法：

void insert(Item item){    
    assert( count + 1 <= capacity );    
    data[count+1] = item;    
    count ++;    
    shiftUp(count);    
}

可以看出，insert方法首先在data结尾放置了新的item元素，之后使用shiftUp来维护data数组的最大堆的性质。

我们来看shiftUp函数：

void shiftUp(int k){    
    while( k > 1 && data[k/2] < data[k] ){    
        swap( data[k/2], data[k] );    
        k /= 2;    
    }    
}

可以看出，我们实现的这个shiftUp元素，是在 data[k/2] < data[k] 的时候，进行swap操作。这就回答了你的问题，当碰到一个元素，这个元素和它的父亲节点元素的值一样的时候，是不会发生交换的：）

不过，对于堆排序，由于其本身不是稳定排序，所以，在这里，将循环条件写成：

while( k > 1 && data[k/2] <= data[k] )

也是正确的。只不过在相同元素的时候多交换一次而已：）

另外一个验证这个问题的方法是：构建一个非常简单的测试用例测试一下。比如堆中就一个元素1，然后向堆中再扔进去一个元素1，看看shiftUp中的swap函数有没有执行？有执行过就说明发生了交换，没有执行过就说名没有发生交换。然后再去深入研究，为什么没有发生交换或者为什么没有发生交换。

计算机属于工科，具有工程性，实验是非常重要的。不要只对着代码看，加一些测试代码实际看看会发生什么，会帮助你更好的理解代码哦：）加油！

2

2

liuyubobobo

回复

魏龙云

加油！：）

2017-07-21

共2条回复