对堆进行排序的最快方法（至少在理论上）是什么？

Question

堆是一个列表，其中以下条件适用：

l[i] <= l[2*i] && l[i] <= [2*i+1]

for 0 <= i << len(list)

我正在寻找就地排序。

Answer 1

只需使用堆排序即可。 它就位了。 这将是最自然的选择。

您也可以只使用您的堆并使用其他算法对其进行排序。 然后，您从排序列表中重新构建堆。 快速排序是一个很好的候选者，因为您可以确定它不会仅仅因为您的堆已经预先排序而以最坏情况的 O(n²) 顺序运行。

如果你的比较函数很昂贵，那可能会更快。 堆排序往往经常评估比较函数。

Answer 2

好吧，通过将数据放在堆中，您已经完成了堆排序的一半。 您只需要实现堆排序算法的第二部分。 这应该比在堆数组上使用快速排序更快。

如果您有勇气，可以尝试实施 smoothsort，对于接近排序的数据，它比堆排序更快。

Answer 3

对堆进行就地排序听起来像是堆排序的工作。

我认为内存是有限的，也许是一个嵌入式应用程序？

Answer 4

既然你已经有了一个堆，你不能只使用堆排序的第二阶段吗？ ？ 它工作到位并且应该是好的和高效的。

Answer 5

对于就地排序，最快的方法如下。 请注意我的代码中的差一错误。 请注意，此方法给出了一个反转的排序列表，需要在最后一步中取消反转。 如果您使用最大堆，这个问题就会消失。

总体思路很简洁：将最小的元素（索引为 0）与堆中的最后一个元素交换，将该元素向下冒泡，直到恢复堆属性，将堆的大小缩小 1 并重复。

正如 David Mackay 演示的那样，这并不是非就地排序的绝对最快方法此处 - 您可以通过将一个更有可能是最小的元素放在堆的顶部而不是底部的元素来做得更好排。

时间复杂度是 T(n.log n) 最坏情况 - n 次迭代，可能有 log n （堆的高度）经历 while 循环。

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

一项一项地读取堆顶部的项目。 基本上你所拥有的是堆排序。