對堆進行排序的最快方式（至少在理論上）是什麼？

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