интерфейс выглядит так
template <class T, class Pred>
void downheap (std::vector<T>& heap_vector, unsigned int startingIndex, Pred predicateFunc);
если startingIndex я сидела К в векторе его оставленный ребенок в куче будет располагаться по индексу (2 * к)
И его правильный ребенок в куче будет располагаться по индексу ((2 * к) + 1).
по существу, элемент должен сравниваться (и при необходимости заменяться) с соответствующим потомком в
кучи до тех пор, пока не будет выполнен заданный порядок функцией предиката.
предикат может быть больше, меньше или любой другой последовательности …
При реализации такого метода, как вы проверяете, что индекс доступа находится в пределах размера? т.е.
heap_vector [rightChildIndex] или же heap_vector [leftChildIndex] не должен выходить за рамки heap_vector.size () — 1 пока зацикливаюсь и делаю сравнение …
это дало мне немного головной боли
вот мой код
while ( pred ( heap_vector[rightChild], heap_vector[parentIndex] ) || pred (
heap_vector[leftChild], heap_vector[parentIndex] ) ) {
if ( pred ( heap_vector[rightChild], heap_vector[leftChild]) ) {
std::swap(heap_vector[parentIndex],heap_vector[rightChild]);
parentIndex=rightChild;
}
else {
std::swap( heap_vector[parentIndex], heap_vector[leftChild]);
parentIndex=leftChild;
}
rightChild= 2*parentIndex+1;
leftChild=2*parentIndex;
if (rightChild>heap_vector.size() || leftChild>heap_vector.size())
break;
}
Задача ещё не решена.
Других решений пока нет …