Почему мой HeapSort пропускает первый элемент в массиве?

Question

Почему мой HeapSort пропускает первый элемент в массиве?

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

Исходный массив:

int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };

Вывод после HeapSort ()

5 99 32 15 13 12 8 4 1

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

int main()
{
int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };
HeapSort(heapArray);return 0;

}

……………………………………………………………………………..

void HeapSort(int heapArray[])
{
int heap_size = SIZE;
int n = SIZE;
int temp;

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{
temp = heapArray[1];
heapArray[1] = heapArray[i];
heapArray[i] = temp;

heap_size = heap_size-1;
Max_Heapify(heapArray,1);
}

return;
}

……………………………………………………………………………….

void Build_Max_Heap(int heapArray[])
{
double n = SIZE;

for(double i = floor((n-1)/2); i >= 1; i--)
{
Max_Heapify(heapArray,i);
}

return;
}

……………………………………………………………………………….

void Max_Heapify(int heapArray[],int i)
{
int n = SIZE;
int largest = 0;
int l = Left(i);
int r = Right(i);

if(( l <= n) && (heapArray[l] > heapArray[i]))
{
largest = l;
}
else
{
largest = i;
}

if( (r <= n) && ( heapArray[r] > heapArray[largest]))
{
largest = r;
}

int temp;
if(largest != i)
{
temp = heapArray[i];
heapArray[i] = heapArray[largest];
heapArray[largest] = temp;

Max_Heapify(heapArray,largest);
}

return;
}

……………………………………………………………………………….

int Parent(int i)
{
return (i/2);
}

int Left(int i)
{
return (2*i);
}

int Right(int i)
{
return ((2*i)+1);
}

-1

c++heapsort

Решение

Другие решения

Вот

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{                 ^^^^^
temp = heapArray[1];
heapArray[1] = heapArray[i];
heapArray[i] = temp;

heap_size = heap_size-1;
Max_Heapify(heapArray,1);
}

return;
}

Вы останавливаете цикл для i = 2, уменьшаете его до 1, не берете первый элемент heapArray, который индексируется 0

0

Parent, Left а также Right функции подходят для массивов на основе 1. Для 0-основе вам нужно использовать:

int Parent(int i)
{
return (i - 1) / 2;
}

int Left(int i)
{
return (2 * i) + 1;
}

int Right(int i)
{
return 2 * (i + 1);
}

Как вы можете проверить на примере кучи:

0

Источник

Accepted Answer

У вас есть несколько проблем в вашем коде:

Во-первых: индексы массива начинаются с 0, а не с 1, поэтому есть много мест, где ошибки индекса перечислены следующим образом:

В функции HeapSort:

for(int i = n-1; i >= 2; i--)  {
//should be 1 not 2
temp = heapArray[1]; //should be 0 not 1 in those 2 statements
heapArray[1] = heapArray[i];
heapArray[i] = temp;
}

Max_Heapify(heapArray,1);
//should start from 0 not 1

Кроме того:

for(double i = floor((n-1)/2); i >= 1; i--)
{                             //should start from 0 not 1
Max_Heapify(heapArray,i);
}

У вас, Parent, Left и Right, есть похожие ошибки, вы можете увидеть два вышеупомянутых поста.

Между тем, у вас есть логические ошибки в функциях HeapSort и Max_Heapfiy.
Вы определяете heap_size и обновляете его, но никогда не использовали его. Вы должны передать его в функцию Max_Heapify. Поскольку каждый раз, когда вы помещаете текущий наибольший элемент в конец массива, вам нужно только накапливать оставшиеся элементы, а не целую кучу. Это также означает, что ваша функция heapify содержит ошибки, поскольку вы никогда не использовали heap_size. Правильные HeapSort и Max_Heapify, а также функция Build_Max_Heap должны быть:

Пирамидальная сортировка:

void HeapSort(int heapArray[])
{
//do what you did before this sentence
Build_Max_Heap(heapArray,heap_size);
//need to pass heap_size since Max_Heapify use heap_size
for(int i = n-1; i >= 1; i--)
{
//...same as you did but pay attention to index
heap_size = heap_size-1;
Max_Heapify(heapArray,0,heap_size); //remember to use heap_size
}
//you declared void, no need to return anything
}

Функция Build_Max_Heap:

void Build_Max_Heap(int heapArray[], int heapSize) //should use heapSize
{
int n = SIZE;
for(int i = floor((n-1)/2); i >= 0; i--) //here should be 0 not 1
{
Max_Heapify(heapArray,i,heapSize); //should use heapSize
}
}

Функция Max_Heapify:

void Max_Heapify(int heapArray[],int i, int heap_size) //should use heap_size
{
//....here similar to what you did
if(( l < heap_size) && (heapArray[l] > heapArray[i]))
{   //^^compare with heap_size not SIZE
//skip identical part
}

if( (r < heaps_ize) && ( heapArray[r] > heapArray[largest]))
{
//same error as above
}

//skip identical part again
Max_Heapify(heapArray,largest, heap_size); //have to use heap_size
}
}

Возможно, вам придется лучше понять алгоритм HeapSort из псевдокода.

1