힙 정렬 (Heap Sort)

힙 정렬를 짜보았다.

특징은  n에 대하여 2n은 차일드 왼쪽, 2n+1은 차일드 오른쪽이다.

즉 10개의 칸이 있다고 가정하면, 1번째 칸의 자식은 2(2n)와 3(2n+1)이다. 

마찬가지로 5번째 칸의 자식은 10(2n) 11(2n+1)이다.

위에 성질이 성립할려면 배열 0번째를 비우고 1번째 부터 채워나가야 한다.(0에 2를 곱해봐야 0이니까 성립X)

http://egloos.zum.com/springmvc/v/568876

상단의 주소에서 알고리즘을 참고하여 작성하였으나

암만 봐도 뭔가 내가 이해를 잘못한건지 이상해서 디버깅을 좀 하였다....

위 주소의 알고리즘과 컨셉은 동일하다.

위 알고리즘의 컨셉은 제일 마지막 부모부터 순서대로 힙의 성질과 맞는지 확인한다.

즉 10개의 원소가 있으면 마지막 부모는 배열 중 5번째이다.

(2n, 2n+1의 성질을 생각해보면 마지막 부모는 총 원소 개수에서 나누기 2로 구할 수 있다.)

 5번째 부모와 자식간의 관계가 힙이 아닌지 맞는지 확인 후

힙이 아니면 스왑을 한다. (즉 5번째 원소와 10번째 원소 크기를 비교한다는 말)

그렇게 스왑을 한 후 4번째 부모를 확인하고 또 다시 스왑, 3번째 부모도 동일...

반복하다가 만약 1번째 부모가 너무 커서 3번 자식과 스왑을 했는데 스왑된 놈 너무 커서 또 6번이랑 스왑을 해야 하는 상황이 오면 

if(heap[smaller] < heap[n])

{

swap(heap, smaller, n);

fixHeap(heap, smaller, heapSize);

}

이 위의 소스가 알아서 재귀적으로 계속 바꿔 나간다.

이걸 이해했으면 블로그의 글쓴이가 왜 마지막 부모부터 차례로 해야하는지 이해를 했을 것이다.

#include <stdio.h>

#include <stdlib.h>

void constructHeap(int *heap, int heapSize);

void swap(int *heap, int smaller, int n);

void fixheap(int *heap, int n, int last);

int main()

{

int heapSize = 0;

int *heap = NULL;

int i = 0;

printf("Put in the number of elements : ");

fflush(stdout);

scanf("%d", &heapSize);

heapSize++;

if(heapSize < 0)

{

printf("No Zero Size Heap");

exit(0);

} //no elseStatement

heap = (int *)malloc(sizeof(int) * heapSize);

for(i = 1; i < heapSize; i++)

{

printf("Input the number %d element :", i);

fflush(stdout);

scanf("%d", &heap[i]);

}

printf("\n");

printf("Inital array : ");

for(i = 1; i < heapSize ; i++)

{

printf("%d ", heap[i]);

}

constructHeap(heap, heapSize);

printf("\n");

printf("Heap Sort Result : ");

for(i = 1; i < heapSize; i++)

{

printf("%d ", heap[i]);

}

return 0;

}

void swap(int *heap, int smaller, int n)

{

int temp = 0;

temp = heap[smaller];

heap[smaller] = heap[n];

heap[n] = temp;

}

void constructHeap(int *heap, int heapSize)

{

int i = 0;

for(i = heapSize / 2; i > 0; i--)

{

fixHeap(heap, i, heapSize);

}

}

void fixHeap(int *heap, int n, int heapSize)

{

int left = 2 * n;

int right = 2 * n  + 1;

int smaller = 0;

if(heap[right] <= heap[n] && right < heapSize)

{

if(heap[left] < heap[right])

{

smaller = left;

}

else

{

smaller = right;

}

}

else if(heap[left] <= heap[n])

{

smaller = left;

}

else

{

return;

}

if(heap[smaller] < heap[n])

{

swap(heap, smaller, n);

fixHeap(heap, smaller, heapSize);

} //no elsestatement

}