ヒープソートの実装

Question

ソートアルゴリズムの詳細については、プログラムでヒープソートを実装しようとしています。しかし、私は問題に取り組んでいます。

私はこのようにメインでソートヒープを呼ぶ：

メイン：h_vectorはランダムで、ランダムなサイズのベクトルは、要素を命じている

heap_sort(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 *** 

私はこれを引き起こしている可能性がありますかわからないです。私は、最初に私の寓意がベクトルの境界から外れているかもしれないと考えましたが、私は数回チェックして、どこに見えません。何か案は？あなたの助けを前もってありがとう。

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

注：これを見て、right = v.size()

を今すぐ：max_heapify()の非常に最初のinvokationで

Answer 1

、あなたはあなたが実際に設定right = i + 2;設定したときにこのようにi = v.size() - 2

、とそれを呼び出しますそのright <= v.size()となっており、現在は範囲外のv[right]にアクセスしようとしています。 vの最後のインデックスがv[v.size() -1]ある

注こと - ので、すべての文がするかどうright < v.size() [代わりに<=]

私はこれらの問題は最終的にあなたのバグを解決します解決を前提としています。

Answer 2

build_max_heap（）の "for"ループが後方に実行されています。そのようにヒープを構築することはできません。配列の最初の要素をヒープとして開始し、それに後続の要素を追加します。残りの配列はまだヒープではないので、これは最後からは動作しません。

また、amitと言われています。

特に、ヒープは配列とヒープのサイズによって定義されます。ヒープは常にヒープのすべての部分ではないため、配列ではありません。したがって、パラメータ（ヒープサイズ）が不足しています。配列全体がヒープである唯一の時間は、build_max_heap（）が完了した後、2番目のパスを実行してソートされた順に引き出す前です。他のすべての時点で、ヒープサイズは配列サイズではありません。

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