// heapSort_han.c
// 배열과 이진트리를 활용한 힙정렬
// 참고 유튜브 영상: "초이스 프로그래밍"채널의 "[자료구조] 힙 트리/힙 정렬 : 개념과 구현(C언어)"
// 해당 강의의 초반부만 듣고 짜본 소스코드라, 불필요하게 복잡하고 예외처리가 많음.
// 강의에 나온 소스 코드는 "왼쪽 노드를 따라간다"는 핵심적인 원리에 충실하고 child 라는 포인터를 사용해
// 자칫 복잡해질 수 있는 표현식을 간단하게 표현했다.
// 이 코드는 필자의 스타일대로 그냥 작성해본 것이라 범용 사용에는 지장 있을 수 있음.
#include <stdio.h>
#include <stdlib.h>
#define MAX_COUNT 100
typedef struct {
int data[MAX_COUNT];
int size;
} heapType;
void insertHeap(heapType *h, int item) {
int index, tmp;
if (h->size >= (MAX_COUNT - 1)) {
printf("Full!\n");
return;
}
h->size++;
index = h->size;
h->data[index] = item;
// 부모 인덱스에 도착했거나 부모 값이 자식 값보다 더 크다면 빠져나간다
while (index != 1 && (h->data[index / 2]) < h->data[index]) {
// 도중이라면 부모의 값과 자신의 값을 바꾸고 index를 부모의 인덱스로 변경한다.
tmp = h->data[index];
h->data[index] = h->data[index / 2];
h->data[index / 2] = tmp;
index = index / 2; // 부모 인덱스로 이동
}
}
//삭제된 루트 노드의 값을 반환 (max heap이냐 min heap이냐에 따라 최대값 or 최소값이 됨)
int removeHeap(heapType *h) {
int index, result, childNum, tmp;
result = h->data[1]; // 삭제할 최대값을 저장해서 리턴한다.
index = 1; // 현재 위치 root
// 최말단 노드의 값을 root노드에 넣는다.
h->data[index] = h->data[h->size];
h->size -= 1; // 데이터 갯수를 하나 줄였음을 표시
//재정렬한다. 왼쪽 오른쪽 두 데이터를 비교해서 큰 데이터와 자신을 비교해서 자신이 작다면 비교 대상 노드와 값을 교환한다.
// index 는 교체한 자식의 인덱스로 넘어간다.(값 자체가 바뀌었기 때문)
// 노드의 끝이 아니고 자식들 값보다 본인이 작을 동안 루프 // 자식 노드의 개수를 따진다.
while (index <= h->size) { //혹은 while (1)
if ((index * 2 + 1) <= h->size) { // 자식 개수가 2개라면
//왼쪽 값이 오른쪽 값보다 크고 그 왼쪽 값이 부모값보다 크다면 왼쪽값과 부모값 교체
if (h->data[index * 2] >= h->data[index * 2 + 1] && h->data[index * 2] > h->data[index] ) {
printf("자식 개수 2개: %d와 왼쪽 %d를 맞바꾸는 중\n", h->data[index], h->data[index * 2]);
tmp = h->data[index];
h->data[index] = h->data[index * 2];
h->data[index * 2] = tmp;
index = index * 2;
if (index * 2 > h->size) break;
} //오른쪽 값이 왼쪽값보다 크고 왼쪽값이 부모값보다 크다면 오른쪽과 부모값 교환
else if (h->data[index*2+1] >= h->data[index*2] && h->data[index*2+1] > h->data[index]) {
printf("자식 개수 2개: %d와 오른쪽 %d를 맞바꾸는 중\n", h->data[index], h->data[index * 2 + 1]);
tmp = h->data[index];
h->data[index] = h->data[index * 2 + 1];
h->data[index * 2 + 1] = tmp;
index = index * 2 + 1;
if (index * 2 + 1 > h->size) break;
}
else { // 자식값보다 부모값이 크므로 변동 없이 중료
break;
}
} // 자식 개수가 1개고 자식값이 크다면 왼쪽과 교체한다.
else if (index * 2 <= h->size && h->data[index * 2] > h->data[index]) {
printf("자식 개수 1개: %d와 왼쪽 %d를 맞바꾸는 중\n", h->data[index], h->data[index * 2]);
tmp = h->data[index];
h->data[index] = h->data[index * 2];
h->data[index * 2] = tmp;
index = index * 2;
if (index * 2 > h->size) break;
}
else if (index*2 <= h->size && h->data[index*2] < h->data[index]) {
break;
}
}
return result;
}
//출력한 개수, 데이터의 개수를 리턴한다.
int printTree(heapType *h) {
int i;
for (i = 1; i <= h->size; i++) {
printf("%d ", h->data[i]);
}
return --i;
}
void main() {
heapType heap;
heap.size = 0;
int values[] = { 17, 29, 27, 15, 34, 33, 37, 43, 12, 24};
for (int i = 0 ; i < sizeof(values) / sizeof(int); i++) {
insertHeap(&heap, values[i]);
}
printTree(&heap);
printf("\n\n");
for (int i = 0; i < 4; i++) { //4개를 삭제
printf("가져온-삭제된- 값은 %d\n", removeHeap(&heap));
printf("전체 원소수: %d개 \n\n", printTree(&heap));
}
return 0;
}
-----실행 결과 ------
43 37 34 29 24 27 33 15 12 17
자식 개수 2개: 17와 왼쪽 37를 맞바꾸는 중
자식 개수 2개: 17와 왼쪽 29를 맞바꾸는 중
가져온-삭제된- 값은 43
37 29 34 17 24 27 33 15 12 전체 원소수: 9개
자식 개수 2개: 12와 오른쪽 34를 맞바꾸는 중
자식 개수 2개: 12와 오른쪽 33를 맞바꾸는 중
가져온-삭제된- 값은 37
34 29 33 17 24 27 12 15 전체 원소수: 8개
자식 개수 2개: 15와 오른쪽 33를 맞바꾸는 중
자식 개수 2개: 15와 왼쪽 27를 맞바꾸는 중
가져온-삭제된- 값은 34
33 29 27 17 24 15 12 전체 원소수: 7개
자식 개수 2개: 12와 왼쪽 29를 맞바꾸는 중
자식 개수 2개: 12와 오른쪽 24를 맞바꾸는 중
가져온-삭제된- 값은 33
29 24 27 17 12 15 전체 원소수: 6개