排序堆的最快方法(至少在理论上)是什么?

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

您也可以使用堆,并使用其他算法对其进行排序。然后,根据排序列表重新构建堆。快速排序是一个很好的选择,因为您可以确保它不会以最坏的O(n)顺序运行,因为您的堆已经预先排序。

如果比较函数比较昂贵,则速度可能会更快。堆排序通常会计算比较函数。

smoothsort ,对于几乎已排序的数据,其速度比heapsort快。

在适当的位置对堆进行排序听起来像是一项工作 Heap Sort .

heap sort ? 它在适当的地方工作,应该是好的和有效的。

一般的想法很简洁:将最小的元素(索引为0)与堆中的最后一个元素交换,将该元素向下冒泡,直到恢复heap属性,将堆的大小缩小1,然后重复。

正如David Mackay所演示的,这并不是非就地排序的最快方法 here -您可以将一个更可能是最小的元素放在堆的顶部,而不是放在最下面一行。

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--:
  }

逐个读取堆顶部的项目。基本上就是堆排序。