Сортировка кучи не дает правильного вывода
Я пишу функцию для сортировки массива, используя сортировку кучи. Пока что у меня есть:
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;
}
}
Когда я запускаю программу, она выводит некорректно отсортированный массив. Есть ли что-то, что я просто пропускаю или какая-то ошибка, которую я упустил из виду?
Решение
Всего несколько предложений.
Во-первых, я бы написал небольшой прокси-класс, который ничего не делает, но позволяет вам использовать индексирование на основе 1 для вашей коллекции. Вся математика индекса, используемая в кучах, предполагает индексирование на основе 1, и гораздо проще компенсировать индексацию на основе 0 в одном месте, чем во всем коде. В настоящее время у меня достаточно трудного времени после индексации, чтобы убедиться, что вы reheapify_down верно. Это, конечно, правильная общая идея, но потребовалось бы много работы, чтобы убедиться, что вся математика верна.
Во-вторых, я бы написал check_heap (или что-то еще), что вы можете использовать для проверки обоих make_heap и ваш reheapify_down (Кроме того, я бы выбрал либо «make_heap», либо «heapify», поэтому имена будут либо «make_heap» и «remake_heap», либо «heapify» и «reheapify»).
Помимо этого, однако, трудно быть уверенным в проблеме, тем более что вы не включили код для своего make_heap в вопросе. Если это не работает правильно, у остальных нет надежды.
Другие решения
Других решений пока нет …