自下而上HeapSort与自上而下HeapSort (性能方面)

Question

自下而上的HeapSort和自上而下的HeapSort之间的性能差异是什么？

Answer 1

堆是一棵二叉树；因此，我们知道它有log深度，每个级别有2^i个节点。级别0(根)有1个节点，级别1有2个节点，级别2有4个节点，依此类推。

现在考虑一下你提到的两种方法：

对于自下而上，我们将节点插入到底部，并让它们每次在堆中“冒泡”。相反，对于自上而下，我们让节点“倒下”到它们正确的位置。哪一个更有效率？

让我们考虑一下最坏的情况：

在自下而上的模式中，每个节点都可以上升到最高级别。在级别1，这需要一个交换(在两个节点上)；在级别2，这需要两个(在四个节点上)...一旦我们到达最后一级，我们必须进行log n交换(在相当大的n/2个节点上)！这给了我们O( n )效率。

自上而下:在每个级别，任何节点都可以落到树的底部(log n交换)。它与自下而上的区别在于，随着最大坠落距离的增加，受其影响的潜在节点数量会减少。级别0是唯一可以落入log n的级别，并且只有一个节点(而不是自下而上的n/2 )。因此，所有“下降”的总和是O(n)，它是更有效的算法。