构建一个MAX堆树,我们可以使用
现在我们只需要这样做
现在,如果我们使用
我的问题是:当我们使用
siftDown
或siftUp
。通过sift down,我们从根节点开始,将其与其两个子节点进行比较,然后用两个子节点中的较大元素替换它;如果两个子节点都比它小,则停止比较,否则继续将该元素向下筛选,直到达到叶节点(或者当然,直到该元素比其两个子节点都大)。现在我们只需要这样做
n/2
次,因为叶节点的数量是n/2
,并且当我们完成最后一个元素的堆化时,在最后一层(即叶节点之前的那一层)之前,所有叶节点都将满足堆属性 - 因此我们将剩下n/2
个元素需要进行堆化。现在,如果我们使用
siftUp
,我们将从叶节点开始,最终需要堆化所有n
个元素。我的问题是:当我们使用
siftDown
时,我们不是基本上要做两次比较(将元素与其两个子节点进行比较),而使用siftUp
时只需进行一次比较(将该元素与其一个父节点进行比较)吗?如果是的话,这不意味着我们正在将复杂度加倍,并最终以与sift down完全相同的复杂度结束吗?