要构建最大堆树,我们可以siftDown或siftUp通过筛选下来,我们从根开始,并将它与它的两个孩子,那么我们有两个孩子的更大的元素替换它,如果这两个孩子是小然后我们停下来,否则我们继续筛选那个元素直到我们到达一个叶子节点(或者当然再次,直到该元素大于它的两个子节点).
现在我们只需要做那些n/2时间,因为叶子的数量是n/2,当我们完成堆积最后一个元素(在叶子之前)之前的水平上时叶子将满足堆属性 - 所以我们将留下n/2要堆积的元素.
现在,如果我们使用siftUp,我们将从叶子开始,最终我们将需要堆积所有n元素.
我的问题是:当我们使用时,我们siftDown不是基本上进行两次比较(将元素与其两个子元素进行比较),而不是在使用时只进行一次比较siftUp,因为我们只将该元素与其父元素进行比较？如果是的话,那是不是意味着我们将复杂性提高一倍并最终达到与筛选相同的复杂性？