Не удалось найти ошибку в моем коде сортировки кучи. Не выполняется должным образом. C ++ - PullRequest
Новая
       14

Не удалось найти ошибку в моем коде сортировки кучи. Не выполняется должным образом. C ++

0 голосов
/ 14 февраля 2020

Пожалуйста, помогите. Я просмотрел его и, похоже, пропустил ошибку. Кажется, он выходит из функции Max_Heapify и не запускает мой второй l oop для печати отсортированного массива. Это было для задания, которое я уже сдал, но я пытаюсь понять ошибку моих способов, чтобы убедиться, что я могу хорошо выполнить тест. 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

// declare global variable of heap size 
int heap_size = 7;


// function to determine left child node of the tree 
int Left(int i){
    return 2*i+1;
}

// function to determine right child node of the tree 
int Right(int i){
    return 2*i + 2;
}

// create heap tree 
void Max_Heapify (int array[], int index){
    int left_child_index = Left(index);
    int right_child_index = Right(index);
    int largest; 

    // check if left child is smaller than heap size and if left child is bigger than parent
    // if so, save variable as largest value, otherwise, largest value will stay as index
    if ( (left_child_index < heap_size) && (array[left_child_index] > array[index]) )
        largest = left_child_index;
    else largest = index;
    // check if right child is smaller than heap and if bigger than largest value
    if ((right_child_index < heap_size) && (array[right_child_index] > array[largest]) )
        largest = right_child_index;
    // exchange largest values 
    if (largest != index)
        swap(array[index], array[largest]);


    Max_Heapify(array,largest);

}

// check leaves 
void Build_Max_Heap(int array[]){

    for (int i = (heap_size / 2 ) - 1; i >= 0; i--)
        Max_Heapify (array, i);
}


void Heapsort(int array[]) {
    Build_Max_Heap(array);
    for (int i = heap_size-1; i >= 0; i--){
        swap(array[0], array[i]);
        Max_Heapify(array,0);
    }
}

int main(){

    int arr[7] = {21, 9, 50, 7, 6, 33, 77};

    cout << "Non Heapified Array: " << endl;
    for (int i = 0; i < heap_size; i++){
        cout << arr[i] << endl;
    }

    Heapsort(arr);

    for (int i = 0; i < heap_size; i++){
        cout << arr[i]<< endl;
    }


}

1 Ответ

1 голос
/ 14 февраля 2020

Ваш MaxHeapify никогда не заканчивается. Вы должны звонить MaxHeapify, только если largest не i. Если largest равно i, то здесь ничего не нужно делать, поскольку элементы уже сложены. 

if (largest != index){
    swap(array[index], array[largest]);
    Max_Heapify(array,largest);
}
...