堆排序不產生正確的輸出

我正在寫一個函數來使用堆排序來排序數組。到目前爲止，我有：堆排序不產生正確的輸出

template <typename Item, typename SizeType> 
void heap_sort(Item data[], SizeType size) { 
vector<int> v(data,data+size); 
SizeType unsorted = size; 

make_heap(v.begin(),v.end()); 

while(unsorted > 1) { 
    --unsorted; 
    swap(data[0], data[unsorted]); 
    reheapify_down(data,unsorted); 
} 
}

和：

template <typename Item, typename SizeType> 
void reheapify_down(Item data[], SizeType size) { 
SizeType current(0), big_child; 
bool heap_ok = false; 

while(!heap_ok && 2*current+1 < size) { 
    if(2*current+2 > size) 
     big_child = 2*current + 1; 
    else if(data[2*current+1] > data[2*current+2]) 
     big_child = 2*current+1; 
    else 
     big_child = 2*current + 2; 

    if(data[current] < data[big_child]) { 
     swap(data[current],data[big_child]); 
     current = big_child; 
    } 
    else 
     heap_ok = true; 
} 
}

當我運行程序，它雖然輸出正確排序的數組。有什麼我只是失蹤或我忽略了一些錯誤？

來源

2012-12-06 Brandon Bosso

給我們一些樣本輸入和輸出。 –

那麼我的程序已經排序了一組隨機生成的整數值到現在爲止，但隨機數組的大小爲10的輸出如下所示：0424488971. –

我現在要通過並設置一個測試數組來查看它產生的結果。 –

只是一些建議。

首先，我會寫一個小的代理類，它什麼都不做，只是讓你在你的集合上使用基於1的索引。堆中使用的所有指數數學都假定基於1的索引，並且在一個地方比在所有代碼中補償基於0的索引要容易得多。就目前而言，我有足夠的時間來檢索索引，以確保您的reheapify_down是正確的。這當然是正確的一般想法，但要確定所有的數學都是正確的，需要做大量的工作。

其次，我會寫一個check_heap（或其他），你可以用它來驗證你都和make_heap您reheapify_down（順便說一句，我在任「make_heap」決定或「heapify」，所以名稱將會是「make_heap」和「remake_heap」，或者「heapify」和「reheapify」）。

但是，除此之外，很難確定問題，特別是因爲您沒有在問題中包含您的make_heap的代碼。如果它不能正常工作，其他人就沒有希望了。

來源

2012-12-06 21:54:26

堆排序不產生正確的輸出

回答

相關問題