힙 정렬 구현

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()이 완료된 후 두 번째 패스를 실행하여 정렬 된 순서로 가져옵니다. 매번 힙 크기는 배열 크기가 아닙니다.

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