实现堆排序

Question

我正尝试在我的程序中实现堆排序，以了解更多有关排序算法的信息。然而，我正在讨论一个问题。

我主要是这样称呼堆排序的：

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

build_max_heap()中的"for“循环正在向后运行。你不能用那种方式建一个堆。首先将数组的第一个元素作为堆，然后向其添加后续元素。由于数组的其余部分还不是堆，所以从末尾开始就不能工作了。

还有阿米特说的话。

特别是，堆将由数组和堆的大小来定义，而不是数组，因为它并不总是堆的所有部分。所以您缺少了一个参数(堆大小)。整个数组唯一的时间是堆，这是在完成build_max_heap()之后，在运行第二次传递以将其拖入排序顺序之前。在其他时间，堆大小不是数组大小。

Answer 3

#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;
}