实现堆排序

Question

我正在尝试在我的程序中实现堆排序以了解有关排序算法的更多信息。但是我遇到了一个问题。

我叫堆排序的主要是这样的：

主营：

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()最先invokation，你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; 
}