ヒープソートを使用して配列をソートする関数を作成しています。これまでのところ、私は持っています:
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;
}
}
プログラムを実行すると、正しくソートされていない配列が出力されます。見逃しているものや見落としているエラーはありますか?