Поддержание минимальной кучи при удалении переполнения стека
Прецедент:
8,7,5,2,3,6,9 (НЕ min heap) (это элемент A * для функции buildHeap)
2,3,5,7,8,6,9 (минимальная куча после вызова кучи сборки)
3,5,6,7,8,9 (после вызова deleteMin) ЭТО НЕПРАВИЛЬНО
должно быть это 3,7,5,9,8,6
Кажется, я не могу найти проблему с deleteMin, я знаю, что моя heapify работает, но idk, возможно, я чего-то не вижу.
Element Heap::deleteMin(Heap& heap){
Element deleted = heap.H[0];
heap.H[0] = heap.H[heap.size-1];
heap.size--;
cout<<deleted.getKey()<<" has been deleted from heap"<<endl;
for(int i=heap.capacity/2-1;i>=0;--i)
heapify(heap,i);
return deleted;
}
void Heap::heapify(Heap& heap,int index){
int smallest = 0;
int left = 2*index;
int right = 2*index+1;
if(left < heap.size && heap.H[left].getKey() < heap.H[index].getKey())
smallest=left;
else
smallest=index;
if(right < heap.size && heap.H[right].getKey() < heap.H[smallest].getKey())
smallest=right;
if(smallest != index){
int swapKey = heap.H[index].getKey();
heap.H[index].setKey(heap.H[smallest].getKey());
heap.H[smallest].setKey(swapKey);
heapify(heap,smallest);
}
}void Heap::buildHeap(Heap& heap, Element* A){
for(int j=0;j<heap.capacity;++j){
heap.insert(heap,A[j]);
for(int i=heap.capacity/2-1;i>=0;--i)
heapify(heap,i);
}
}
Решение
Первая проблема заключается в том, что ваши вычисления для дочерних индексов неверны. Если вы используете H[0] как корень кучи, то
left = (2*index)+1
right = (2*index)+2
В расчетах вы предполагаете, что корень находится на H[1],
Другая проблема заключается в том, что вы делаете слишком много работы в своем deleteMin функция:
Element Heap::deleteMin(Heap& heap){
Element deleted = heap.H[0];
heap.H[0] = heap.H[heap.size-1];
heap.size--;
cout<<deleted.getKey()<<" has been deleted from heap"<<endl;
for(int i=heap.capacity/2-1;i>=0;--i)
heapify(heap,i);
return deleted;
}
После того как вы удалите минимальный элемент и поместите последний элемент в кучу в корень, вам просто нужно позвонить heapify(heap, 0); Нет причин перестраивать всю кучу в этом цикле.
Итак, ваша функция становится:
Element Heap::deleteMin(Heap& heap){
Element deleted = heap.H[0];
heap.H[0] = heap.H[heap.size-1];
heap.size--;
cout<<deleted.getKey()<<" has been deleted from heap"<<endl;
heapify(heap, 0);
return deleted;
}
Ваш buildHeap Метод также делает слишком много работы.
Возможно, вас заинтересует переподготовка кучи. Моя статья в блоге на http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/ объясняет их работу очень простыми словами, и мой простая куча целых чисел показывает голую реализацию. Это на C #, а не на C ++, но код очень похож. Вы должны быть в состоянии понять это без проблем.
Другие решения
Других решений пока нет …