[Data Structure] 히프 정렬

[Data Structure] 히프 정렬

728x90

히프 정렬 (최대 히프)

n개의 요소를 O(nlog₂n) 시간 안에 정렬

시간 안에 정렬 정렬되지 않은 배열 element a[]에 대하여

→ 배열 a의 data들을 최대 히프에 차례대로 추가

→ 최대 히프에서 data들을 하나씩 꺼내서 배열 a의 맨 뒤쪽부터 저장

→ 배열 a에 대한 히프 정렬 완료

void heap_sort(element arr[], int len) { heapnode* h; h = create(); init_heap(h); for (int i = 0; i < len; i++) { insert_node(h, arr[i]); } for (int i = (len - 1); i >= 0; i--) { arr[i] = delete_node(h); } free(h); // 히프 동적 할당 해제 }

※ Example

#include #include // 히프 정렬 #define MAX_HEAP_SIZE 100 typedef int element; // 히프에 저장된 각 요소들 typedef struct heepnode { element heap[MAX_HEAP_SIZE]; int heap_size; }heapnode; heapnode* create() { return (heapnode*)malloc(sizeof(heapnode)); } void init_heap(heapnode* h) { h->heap_size = 0; } int is_empty(heapnode* h) { return h->heap_size == 0; } int is_full(heapnode* h) { return h->heap_size == MAX_HEAP_SIZE - 1; } void insert_node(heapnode* h, element item) { if (is_full(h)) { fprintf(stderr, "Error : Heap is full

"); return; } else { int i; // item의 인덱스 i = ++h->heap_size; // item인덱스 = 현재 히프트리에 있는 최종 item 인덱스의 다음 인덱스 while (i != 1 && (item > h->heap[i / 2])) { h->heap[i] = h->heap[i / 2]; i /= 2; } h->heap[i] = item; } } element delete_node(heapnode* h) { if (is_empty(h)) { fprintf(stderr, "Error : Heap is empty

"); return; } else { element root = h->heap[1]; // 루트 노드 item element last = h->heap[h->heap_size--]; // 말단 노드 item // 루트 노드를 삭제시키고 말단을 루트로 올릴거기 때문에 heap_size는 1 감소 int index = 1; // 말단 노드가 들어가는 index -> 자리 찾을 때 까지 계속 변함 int child = 2; while (child <= h->heap_size) { if ((child < h->heap_size) && (h->heap[child] < h->heap[child + 1])) child++; // 자식 노드 중 더 큰 값의 인덱스 찾기 if (last >= h->heap[child]) break; // 최종 insert 노드의 값이 해당 인덱스의 자식 값보다 크면 더 이상 옮기기 X h->heap[index] = h->heap[child]; index = child; child *= 2; } h->heap[index] = last; return root; } } void heap_sort(element arr[], int len) { heapnode* h; h = create(); init_heap(h); for (int i = 0; i < len; i++) { insert_node(h, arr[i]); } for (int i = (len - 1); i >= 0; i--) { arr[i] = delete_node(h); } free(h); // 히프 동적 할당 해제 } int main(void) { element arr[] = { 289, 30, 1, 2, 6, 79, 59, 17, 20, 100}; int len = sizeof(arr) / sizeof(int); printf("배열 요소 개수 : %d

", len); printf("정렬 전 배열 arr 요소 : "); for (int i = 0; i < len; i++) { printf("[%d] ", arr[i]); } printf("

"); heap_sort(arr, len); printf("정렬 후 배열 arr 요소 : "); for (int i = 0; i < len; i++) { printf("[%d] ", arr[i]); } }

728x90

반응형

from http://cs-ssupport.tistory.com/174 by ccl(A) rewrite - 2021-12-19 15:27:04