Сортировка кучи не работает или неверный расчет

Question

Функция max-heap работает нормально, но не работает heapsort.

Когда я запускаю этот код. показывает неверный расчет.

Your input is:
9 79 42 86 33 75

Your max-heap is:
86 79 42 75 33 9

Ascending numerical order:
86 79 42 75 33 9

Как вы можете видеть в моем последнем выводе, порядок возрастания чисел совпадает со значением max-heap, но это не то, чего я ожидаю.

Моя задача состоит в том, чтобы мне пришлось отсортировать число из максимальной кучи. Кроме того, я должен поменять местами первый и последний элемент из массива max-heap, а затем проигнорировать последний элемент. Кроме того, как только последний элемент игнорируется, мне снова нужно выполнить функцию max-heap.

Пример того, как работает расчет. max-heap: 86, 79, 42, 75, 33, 9. В разделе сортировки я должен поменять местами первый и последний элемент, а затем проигнорировать последний элемент, поэтому результат сортировки кучи должен быть: 9, 79, 42 , 75, 33, [86] (квадратная скобка означает игнорирование или удаление) . Я должен сделать максимальную кучу снова из предыдущей сортировки. Второй результат max-heap будет 79, 75, 9, 42, 33. Когда я вернусь к сортировке, я должен поменять местами первый и последний элемент, а затем снова проигнорировать последний элемент, так что max-heap будет 79, 75. , 9, 42, 33 и результат сортировки кучи должен быть: 33, 75, 9, 42, [79], [86]. Я должен сделать один и тот же шаг снова и снова, пока все номера не будут отсортированы.

Пример вывода, на котором я хочу отобразить:

Мой ввод 9, 79, 42, 86, 33, 75

Максимальная куча должна быть: 86, 79, 42, 75, 33, 9.

По возрастанию должно быть: 9, 33, 42, 75, 79, 86.

Для получения дополнительной информации, пожалуйста, посетите веб-сайт https://en.wikipedia.org/wiki/Heapsort#Example, См. Пример 2 - Сортировка

А вот код неверного расчета:

#include "stdafx.h"
#include <iostream>

using namespace std;

int heap[30];

void main()
{
int n, index, parent, flag, dummy;
n = 7; //size of table

// user input number
for (index = 1; index < 7; index++) 
{
    cout << "Enter value " << index << ": ";
    cin >> heap[index];
}

// output for user element
cout << "\nYour input is:\n";
for (index = 1; index < 7; index++) 
{
    cout << heap[index] << " ";
}

flag = 1;

while (flag == 1)
{
    flag = 0;

    //heapify
    for (index = 7; index >1; index--)
    {
        parent = index / 2;
        if (heap[parent] < heap[index])
        {
            dummy = heap[parent];
            heap[parent] = heap[index];
            heap[index] = dummy;
            flag = 1;
        }

        // Sorting --> swap first and last of the array and then ignore the 
        //last array and reheap from above until all number sorted.

        while (heap[0] >= 1)
        {
            int last = heap[0];
            int temp1 = heap[1];
            heap[1] = heap[last - 1];
            heap[last - 1] = temp1;
            heap[0]--;
        }
    }
}

cout << "\n\nYour max-heap is:\n";
for (index = 1; index < 7; index++) // output for after heap
{
    cout << heap[index] << " ";
}

cout << "\n\nAscending numerical order:\n";
for (index = 1; index < 7; index++) //output for sorting.
{
    cout << heap[index] << " ";
}

getchar();
getchar();
}

Также код, который я не могу изменить или заменить который

    while (flag == 1)
{
    flag = 0;

    //heapify
    for (index = 6; index >1; index--)
    {
        parent = index / 2;
        if (heap[parent] < heap[index])
        {
            dummy = heap[parent];
            heap[parent] = heap[index];
            heap[index] = dummy;
            flag = 1;
        }
    }

}

Answer 1

В вашем коде много ошибок.

Первый, который я заметил, находится в вашем цикле while

while (heap[0] >= 1) //heap[0] = 0 since you declared your array statically
    {
        int last = heap[0]; // last = 0
        int temp1 = heap[1];
        heap[1] = heap[last - 1]; //trying to find element heap[-1] ERROR
        heap[last - 1] = temp1; //heap[-1] = heap[1]
        heap[0]--; //heap[0] = -1 why?
    }

Во-вторых, вы начинаете с индекса 1 и переходите к индексу 6 в цикле ввода (сначала для цикла в коде), но когда вы пытаетесь изменить разницу в куче в третьем цикле for, вы начинаете с индекс 7 и вы идете в индекс 2.

Я не смог найти способ в вашем коде, поэтому я опубликую свой. Он следует алгоритму на той вики-странице, которую вы разместили.

#include <iostream>

using namespace std;



void build_heap(int *heap, int index)
{
    if(index>1)
    {
       int new_input = heap[index], tmp = 0;
    //since your index starts from 1 and goes up to n in heap
    //parent from index k is (k%2==1) ? (k-1)/2 : k/2
    if(index % 2 == 1)
        index--;
    if(heap[index/2] < new_input)
    {

        tmp = heap[index/2];
        heap[index/2] = new_input;
        heap[index] = tmp;
        build_heap(heap, index/2);
       }
    }
}

void make_order_in_heap(int *heap, int n)
{
if(n>1)
{
    int index = 1;
    int child_index;
    bool work = true;

    while(work && index < n)
    {
        //finding child_index
        if( index * 2 + 1 <= n)
        {
            child_index = heap[index*2] > heap[index*2+1] ? index*2 : index*2+1;
        }
        else if(index * 2 <= n)
        {
            child_index = index*2;
        }
        else
        {
            //this index has no  children
            return;
        }
        work = false;
        if(heap[child_index] > heap[index])
        {
            int tmp = heap[index];
            heap[index] = heap[child_index];
            heap[child_index] = tmp;
            index = child_index;
            work = true;
        }
    }

}
}

void swap_first_and_last(int *heap, int n)
{
if(n>1)
{
    int tmp = heap[1];
    heap[1] = heap[n];
    heap[n] = tmp;
}
}

void sort_heap(int *heap, int n)
{
if(n>1)
{
    swap_first_and_last(heap, n);
    //we swaped first and last element in heap with n elements
    //so now first element in heap of n-1 elements is not on his      possiton
    make_order_in_heap(heap, n-1);
    sort_heap(heap, n-1);
}
}

int main()
{
int heap[30];
int n, index, parent, flag, dummy;
n = 7; 

for (index = 1; index <= n; index++) 
{
    cout << "Enter value " << index << ": ";
    cin >> heap[index];
    build_heap(heap, index);
}

cout << "\nYour input is:\n";
for (index = 1; index <= n; index++) 
{
    cout << heap[index] << " ";
}


sort_heap(heap, n);

cout << "\n Sorted array is:\n";
for (index = 1; index <= n; index++) 
{
    cout << heap[index] << " ";
}
return 0;
}