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

Question

堆就是应用以下列表：

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

为0 <= i < len(list)

我在寻找就地分拣。

Answer 1

那么你已经是通过堆中的数据堆的一半了。你只需要实现堆排序算法的第二部分。这应该比在堆数组上使用快速排序更快。

如果你感觉很勇敢，你可以在实施smoothsort时采取行动，这对于接近排序的数据来说比heapsort更快。

Answer 2

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

Answer 3

排序堆就地类型的声音像Heap Sort的工作。

我假设内存是受限的，一个嵌入式应用程序，也许？

Answer 4

只需使用堆排序。它在原地。那将是最自然的选择。

你也可以直接使用你的堆，并用其他算法对其进行排序。之后，您将从排序列表重新构建堆。 Quicksort是一个不错的选择，因为你可以确定它不会在最坏的情况下运行O（n2）顺序，因为你的堆已经被预先分类了。

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

Answer 5

既然你已经有一个堆，不能你只需要使用heap sort的第二阶段？它工作到位，应该很好，高效。

Answer 6

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

总的想法是一个整洁的一个：交换的最小元素（索引0处），在所述堆中的元件向下的最后一个元素，气泡直至堆属性被恢复时，由一个并重复缩小堆的大小。

这并不是就地排序的绝对最快的方式，因为David Mackay演示了here - 你可以做的更好一点是将一个元素放在堆的顶部，而不是从堆的顶部最小最下面一排。

时间复杂度是T（n.log n）的最坏的情况下 - n，其中可能的迭代数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--: 
    }