Реализация HeapSort — не в состоянии сортировать согласно ожиданиям
Я пробовал много отладки, используя отладчик и пошаговое выполнение, но кое-как не удалось отсортировать массив в порядке возрастания.
Я реализовал maxHeap и хотел бы отсортировать массив в порядке возрастания.
Вот мой полный код, пожалуйста, скажите, где я не прав.
#include <iostream>
struct maxHeap {
int sizeOfHeap;
int *array;
};
// Ptr to heap
maxHeap *heapPtr = new maxHeap();
//Functions
void heapSort(int *, int );
maxHeap *buildHeap(int *, int);
void heapify(maxHeap *, int);
void swap(int *, int *);
void heapSort(int *inputArray, int size) {
heapPtr = buildHeap(inputArray,size);
while ( heapPtr->sizeOfHeap > 0 ) {
swap(&heapPtr->array[0],&heapPtr->array[size-1]);
--(heapPtr->sizeOfHeap);
//Heapify the root
heapify(heapPtr,0);
}
}
maxHeap *buildHeap(int *inputArray, int size) {
heapPtr->array = inputArray;
heapPtr->sizeOfHeap = size;
for(int i = (size-2)/2; i >= 0; i-- ) {
heapify(heapPtr,i);
}
return heapPtr;
}
//Heapify procedure
void heapify(maxHeap *theHeap, int index) {
int root = index;
int leftChild = (index << 1 ) + 1;
int rightChild = (index << 1 ) + 2;
if ( leftChild < theHeap->sizeOfHeap && theHeap->array[leftChild] > theHeap->array[root] )
root = leftChild;
if ( rightChild < theHeap->sizeOfHeap && theHeap->array[rightChild] > theHeap->array[root] )
root = rightChild;
if ( root != index ) {
swap( &theHeap->array[root], &theHeap->array[index] );
heapify(theHeap,root);
}
}
void swap(int *numOne, int *numTwo) {
int temp = *numTwo;
*numTwo = *numOne;
*numOne = temp;
}Input - 12 11 13 5 6 7
Expected Output - 5 6 7 11 12 13
Output received - 13 11 7 5 6 12
Решение
Обратите внимание, что код завершен: в нем отсутствует main() и структура maxHeapт. е. требуются лишние усилия, чтобы даже воспроизвести проблему. Код явно не имеет никаких признаков отладки, и пошаговое выполнение кода, вероятно, довольно бессмысленно.
Чтобы найти проблему, нужно распечатать содержимое кучи в стратегических точках. Таким образом, вы увидите, что 12 или же 13 как ни странно, остается наверху кучи, указывая на непоследовательное использование размера кучи. В частности, вы должны изменить эти две строки
swap(&heapPtr->array[0],&heapPtr->array[size-1]);
--(heapPtr->sizeOfHeap);
становиться
swap(&heapPtr->array[0], &heapPtr->array[--(heapPtr->sizeOfHeap)];
… или, собственно:
std::swap(heapPtr->array[0], heapPtr->array[--(heapPtr->sizeOfHeap)];
… но тогда это, вероятно, домашнее задание, и вы не можете использовать стандартную библиотеку для реальных операций. В противном случае вы могли бы использовать std::priority_queue<int> или же std::make_heap() а также std::pop_heap(),
Другие решения