Реализация сортировки кучи

Question

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

Я называю сортировку кучи в main следующим образом:

Main:

heap_sort(h_vector);

Где h_vectorвектор случайного размера со случайными упорядоченными элементами.Мой алгоритм сортировки кучи выглядит следующим образом.

Сортировка кучи:

void max_heapify(std::vector<int>& v, int i)
{
    int left = i + 1, right = i + 2;
    int largest;

    if( left <= v.size() && v[left] > v[i])
    {
        largest = left;
    }

    else
    {
        largest = i;
    }

    if( right <= v.size() && v[right] > v[largest])
    {
        largest = right;
    }

    if( largest != i)
    {
        std::swap(v[i], v[largest]);
        max_heapify(v,largest);
    }



}

void build_max_heap(std::vector<int>& v)
{
    for( int i = v.size() - 2; i >= 0; --i)
    {
        max_heapify(v, i);
    }

}

void heap_sort(std::vector<int>& v)
{
    build_max_heap(v);
    int x = 0;
    int i = v.size() - 1;
    while( i > x)
    {
        std::swap(v[i],v[x]);
        ++x;
        --i;
    }

}

Всякий раз, когда я добавляю этот вид сортировки в свою программу, я получаю следующую ошибку.

Ошибка:

*** glibc detected *** ./a.out: free(): invalid next size (normal): 0x096c82d0 ***

Я не уверен, что может быть причиной этого.Сначала я подумал, что мой алогрит может выходить за границы вектора, но я проверил несколько раз, и я не вижу, где.Есть идеи?Заранее спасибо за помощь.

Answer 1

При самом первом вызове max_heapify() вы вызываете его с помощью i = v.size() - 2

Таким образом, когда вы устанавливаете right = i + 2;, вы фактически устанавливаете: right = v.size()

Теперь посмотритепри этом:

 if( right <= v.size() && v[right] > v[largest])

Обратите внимание, что right <= v.size(), и теперь вы пытаетесь получить доступ к v[right], который выходит за пределы.

Обратите внимание, что последний индекс vэто v[v.size() -1] - поэтому все ваши операторы if должны быть right < v.size() [вместо <=]

Я предполагаю, что решение этих проблем в конечном итоге решит вашу ошибку.

Answer 2

#include <stdio.h>
#include <stdlib.h>
int a[90],n;

void swap(int *a,int *b)
 {
   int temp = *a;
        *a = *b;
        *b = temp;
 }
void ct_heap(int n)
{
 int j,data,i;
 for(i=0;i<n;i++)
 {
  data=a[i];
   for(j=i;j>0;j--)
   {
    if(a[(i-1)/2]<data)
     {
       swap(&a[(i-1)/2],&a[i]);
       i=(i-1)/2;
     }
   }
 }
}
void display()
{
  int k;
   for(k=0;k<n;k++)
    {
     printf("%d\t",a[k]);
    }
   printf("\n");
 }
void heap_sort()
{
ct_heap(n);
int end;
end=n-1;

while(end>=0)
  {
    swap(&a[end],&a[0]);

    ct_heap(end);
    end=end-1;
  }
}
int main()
{
    int i;

      printf("Enter Number of Nodes\n");
      scanf("%d",&n);
      printf("Enter Data\n");
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);
      printf("After Heap Creation\n");
      ct_heap(n);
      display();
      heap_sort();
      printf("Array After Heap Sort\n");
      display();
    return 0;
}

Answer 3

Ваш цикл for в build_max_heap () работает в обратном направлении. Вы не можете построить кучу таким образом. Вы начинаете с первого элемента массива в виде кучи, а затем добавляете в него последующие элементы. Это не работает, начиная с конца, потому что остальная часть массива еще не куча.

Кроме того, что сказал Амит.

В частности, куча будет определяться массивом и размером кучи, а не массивом, потому что это не всегда ВСЕ часть кучи. Таким образом, вы пропускаете параметр (размер кучи). Единственный раз, когда весь массив представляет собой кучу, происходит после того, как build_max_heap () завершена, и перед тем, как запустить второй проход, чтобы вывести его в отсортированном порядке. В любое другое время размер кучи не является размером массива.