Сортировка кучи в C ++

Question

Хорошо, так что после попыток отладки я наконец сдался. Я новичок в C ++ и структурах данных, и я пытаюсь реализовать сортировку кучи в C ++. Приведенный ниже код дает правильный вывод о положительных целых числах, но, похоже, не получается, когда я пытаюсь ввести несколько отрицательных целых чисел.

Пожалуйста, укажите ЛЮБЫЕ ошибки / несоответствия в следующем коде. Кроме того, любые другие предложения / критика, имеющие отношение к предмету, будут с благодарностью оценены.

//Heap Sort
#include <iostream.h>
#include <conio.h>
int a[50],n,hs;
void swap(int &x,int &y)
{
    int temp=x;
    x=y;
    y=temp;
}
void heapify(int x)
{
    int left=(2*x);
    int right=(2*x)+1;
    int large;
    if((left<=hs)&&(a[left]>a[x]))
    {
        large=left;
    }
    else
    {
        large=x;
    }
    if((right<=hs)&&(a[right]>a[large]))
    {
        large=right;
    }
    if(x!=large)
    {
        swap(a[x],a[large]);
        heapify(large);
    }
}
void BuildMaxHeap()
{
    for(int i=n/2;i>0;i--)
    {
        heapify(i);
    }
}
void HeapSort()
{
    BuildMaxHeap();
    hs=n;
    for(int i=hs;i>1;i--)
    {
        swap(a[1],a[i]);
        hs--;
        heapify(1);
    }
}
void main()
{
    int i;
    clrscr();
    cout<<"Enter length:\t";
    cin>>n;
    cout<<endl<<"Enter elements:\n";
    for(i=1;i<=n;i++)       //Read Array
    {
        cin>>a[i];
    }
    HeapSort();
    cout<<endl<<"Sorted elements:\n";
    for(i=1;i<=n;i++)       //Print Sorted Array
    {
        cout<<a[i];
        if(i!=n)
        {
            cout<<"\t";
        }
    }
    getch();
}

Я читал о сортировке кучи, но я не могу понять большую часть концепции, и без этого я не могу исправить логическую ошибку (ы) выше.

Answer 1

Вы устанавливаете hs после вызова BuildMaxHeap. Переключите эти две линии.

hs=n;
BuildMaxHeap();

Answer 2

Когда я реализовал свой собственный порт, мне нужно было быть очень осторожным с индексами; если вы индексируете от 0, дети - 2x + 1 и 2x + 2, когда вы индексируете от 1, дети - 2x и 2x + 1. Из-за этого было много тихих проблем. Кроме того, каждая операция нуждается в единственной хорошо написанной функции siftDown, которая является жизненно важной.

Откройте Wikipedia в статьях Heapsort и Binary heap и попробуйте переписать ее более четко, следуя терминологии и обозначениям, где это возможно. Вот моя реализация , возможно, это может помочь.

Хммм, теперь, когда я проверил ваш код лучше, вы уверены, что ваша функция siftDown / heapify ограничивает просеивание до текущего размера кучи?

Редактировать: Нашел проблему! Вы не инициализируете hs в n перед вызовом BuildMaxHeap ().

Answer 3

# include <iostream>   //Desouky//
 using namespace std;

void reheapify(int *arr, int n, int i)
{
int parent = i; // initilaize largest as parent/root
int child1 = 2 * i + 1; // to get first chid 
int child2 = 2 * i + 2; // to get second child

if (child1 < n && arr[child1] > arr[parent]) // if child2 >  parent
{
    parent = child1;
}
//if child > the parent 
if (child2 < n && arr[child2] > arr[parent])
{
    parent = child2;
}
// if the largest  not the parent 
if (parent != i)
{
    swap(arr[i], arr[parent]);
    // Recursively heapify the affected sub-tree
    reheapify(arr, n, parent);
}

}
 void heapsort(int *arr, int n)
 {
 // build a heap
for (int i = n - 1; i >= 0; i--)
{
    reheapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
    // Move current root to end
    swap(arr[0], arr[i]);

    // call max heapify on the reduced heap
    reheapify(arr, i, 0);
 }
 }

 int main()
 {

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
    cin >> arr[i];
}
heapsort(arr, n);
for (int i = 0; i < n; i++)
{
    cout << arr[i] << " ";
}

 }

Answer 4

Вот пример, если это поможет.

#include <iostream>
#include <vector>

using namespace std;

void max_heapify(std::vector<int>& arr, int index, int N) {
    // get the left and right index
    int left_index = 2*index + 1;
    int right_index = 2*index + 2;

    int largest = 0;
    if (left_index < N && arr[left_index] > arr[index]) {
        // the value at the left_index is larger than the 
        // value at the index of the array
        largest = left_index;
    } else {
        largest = index;
    }

    if (right_index < N && arr[right_index] > arr[largest]) {
        // the value at the right_index is larger than the
        // value at the index of the array
        largest = right_index;
    }

    // check if largest is still the index, if not swap
    if (index != largest) {
        // swap the value at index with value at largest
        int temp = arr[largest];
        arr[largest] = arr[index];
        arr[index] = temp;

        // once swap is done, do max_heapify on the index
        max_heapify(arr, largest, N);
    }
}

void build_max_heap(std::vector<int>& arr, int N) {
    // select all the non-leaf except the root and max_heapify them
    for (int i = N/2 - 1; i >= 0; --i) {
        max_heapify(arr, i, N);
    }
}

void heap_sort(std::vector<int>& arr) {
    int N = arr.size();
    int heap_size = N;
    // build the max heap
    build_max_heap(arr, N);

    // once max heap is built,
    // to sort swap the value at root and last index
    for (int i = N - 1; i > 0; --i) {
        // swap the elements
        int root = arr[0];
        arr[0] = arr[i];
        arr[i] = root;

        // remove the last node
        --heap_size;

        // perform max_heapify on updated heap with the index of the root
        max_heapify(arr, 0, heap_size);
    }
}

int main() {
    std::vector<int> data = {5,1,8,3,4,9,10};

    // create max heap from the array
    heap_sort(data);

    for (int i : data) {
        cout << i << " ";
    }

    return 0;
}

Answer 5

Я подозреваю, что это потому, что вы 1-основываете массив. Вероятно, есть случай, когда вы случайно 0-основываете его, но я не могу обнаружить это в коде от руки.