힙 정렬 (Heapsort) 구현

입력 코드 여기힙 정렬 (Heapsort) 구현

# include <iostream> 
# include <stdlib.h> 
# define MAX 10 
void heapsort(int A[]); 
void Build_MAX_Heap(int A[]); 
void MAX_Heapify(int A[],int i); 
int Left(int i); 
int Right(int i); 
void swap(int *num,int *num2); 
using namespace std; 
int main() 
{ 
int H[100],i; 
for(i=0;i<MAX;i++) 
    H[i]=rand(); 
cout << "the given array is::" << " "; 
for(i=0;i<MAX;i++) 
    cout << H[i] << "\n"; 
cout << "\n" << "\n"; 
heapsort(H); 
cout << "the sorted array is ::" << " "; 
for(i=0;i<MAX;i++) 
    cout << H[i] << "\n"; 
} 
void heapsort(int A[]) 
    { 
    int i,heapsize; 
    Build_MAX_Heap(A); 
    for(i=MAX-1;i>0;i--) 
    { 
    swap(&A[0],&A[i]); 
    heapsize=heapsize-1; 
    MAX_Heapify(A,0); 

    } 
} 
void Build_MAX_Heap(int A[]) 
{ 
int heapsize,i; 
heapsize=MAX; 
for(i=(MAX)/2;i>0;i--) 
{ 
    MAX_Heapify(A,i); 
} 
} 
void MAX_Heapify(int A[],int i) 
{ 
int l,r,largest,heapsize; 
l=Left(i); 
r=Right(i); 
if(l<=heapsize && A[l]>A[i]) 
    largest=l; 
else 
    largest=i; 
if(r<=heapsize && A[r]>A[i]) 
    largest=r; 
if(largest!=i) 
{ 
    swap(&A[i],&A[largest]); 
    MAX_Heapify(A,largest); 
} 
} 

int Left(int i) 
{ 
return (2*i); 
} 
int Right(int i) 
{ 
return (2*i+1); 
}

'무효 스왑 (INT * NUM1, INT의 *의 NUM2) {INT 온도; 임시 직원 = * num1; * num1 = * num2; * num2 = 임시; } 내 코드에 무슨 문제가 있나. 정렬되지는 않았지만 정렬 된 주문에는 표시되지 않습니다. 도움말에 대한 감사. 같은 것에 대한 감사합니다.

출처

2015-01-27 Rohit Bharti

코드에 몇 가지 결함이 있습니다.

배열을 1 색인으로 사용하는 경우 왼쪽 자식 (2 * i) 및 오른쪽 자식 (2 * i + 1)의 표기법이 유효합니다. 그러나 배열을 0으로 인덱싱 할 때 왼쪽 자식 = (2 * i + 1), 오른쪽 자식 = (2 * i + 2)로 변경해야합니다.
다음 항목에서 'MAX_Heapify()'함수의 'heapsize'변수가 초기화되지 않았습니다. 할당되지 않은 변수를 사용하고 있는데이 변수는 올바르지 않습니다.
힙 정렬 절차에서 max 요소를 삭제하고 힙의 크기를 줄입니다. 그러나 당신은 어디서나 새로운 크기를 사용하지 않습니다. 프로 시저가 범위를 알 수 있도록 'MAX_Heapify()'에 전달해야합니다.
마지막으로 Build_MAX_Heap (i> = 0)까지 heapify 용 루프를 실행해야한다고 생각합니다. 즉 루트를 포함하여 위의 모든 요소 (MAX/2)에 대해 실행해야합니다.

코드를 수정하고 코드를 다시 작성하면 문제가 없습니다. 스케치와 코드로 이진 힙에 대해 더 자세히 알고 싶으면 내 블로그 게시물 Binary Heaps을 확인하십시오.

제 답변이 도움이 되었기를 바랍니다. ☺

출처

2015-02-10 19:34:10

힙 정렬 (Heapsort) 구현

답변

관련 문제