[C] 우선순위 큐(Heap) 및 Heap Sort 구현
Heapify의 Sift Down동작과 Sift Up동작을 재귀함수로 구현함으로써, heapify
, heap_push
, heap_pop
heap sort
동작을 간결하고 아름답게 구현할 수 있었다. 참고로 코드는 Max Heap을 구현한 내용이다. Min Heap은 각 heapify 함수에서 크기비교 부호만 반대로 하면 된다.
Heapify 힙 구조 생성
Sift Down 방식 Heapify
/**
* heapify sift down
* p
* / \
* l r
*/
void heapify(int arr[], int p_idx, int h_size)
{
int largest = p_idx;
int l_idx = p_idx * 2 + 1;
int r_idx = p_idx * 2 + 2;
/* find a largest one in p,l,r */
if (l_idx < h_size && arr[l_idx] > arr[largest])
largest = l_idx;
if (r_idx < h_size && arr[r_idx] > arr[largest])
largest = r_idx;
if (largest != p_idx) { /* base case */
swap(arr, largest, p_idx); /* swap with larger child */
heapify(arr, largest, h_size); /* heapify agrain from the child */
}
}
void build_heap(int arr[], int h_size)
{
for (int i = (h_size / 2) - 1; i >= 0; i--)
heapify(arr, i, h_size);
}
build_heap
에서 for문이 (h_size / 2) - 1
부터 시작하는 이유. leaf 노드는 heapify sift down을 할 필요가없다. 그래서 자식노드를 가지는 첫번째 노드의 인덱스부터 배열의 인덱스를 하나씩 줄여가면서 heapify를 한다.
참고
heapify()함수 if문에서l_idx < h_size
를 먼저 체크하지 않으면, arr[]에 배열의 인덱스를 넘어가는 값을 참고할 수 있다. if (arr[l_idx] > arr[largest] && l_idx < h_size)
이렇게 구현하면 런타임 에러가 발생한다. 반드시 && 하기 전에 먼저 체크하기.
Heap Pop
int heap_pop(int arr[])
{
int p_idx = 0;
int ret = arr[p_idx];
/* swap last to p_idx */
arr[p_idx] = arr[heap_size - 1];
heap_size--;
/* heapify */
heapify(arr, p_idx, heap_size);
return ret;
}
Heap Push
heap push를 통해 추가된 값은 배열의 맨 끝(트리의 leaf)에 추가되므로, heapify동작은 루트노드부터 시작되는 sift down이 아니라 리프 노드 부터 시작되는 sift up이 되어야한다. 그래서 heapify_siftup() 함수를 아래와 같이 구현함.
void heapify_siftup(int arr[], int curr_idx)
{
int p_idx = (curr_idx - 1) / 2;
if (curr_idx < 1)
return;
if (arr[curr_idx] > arr[p_idx]) {
swap(arr, curr_idx, p_idx);
heapify_siftup(arr, p_idx);
}
}
void heap_push(int arr[], int val)
{
/* insert to the last */
arr[heap_size] = val;
heap_size++;
/* heapify from the last one */
heapify_siftup(arr, heap_size - 1);
}
Heap Sort
heapify
를 구현했으면 Sort는 이제 식은 죽 먹기다. build_heap을 하면 배열의 0번 인덱스는 가장 큰값인데, 이를 배열의 맨 뒤로 swap하고, 배열의 크기를 1씩 줄여서 또다시 heapify하고 위의 내용을 반복하면. 작은 값부터 순차적으로 배열이 오름차순 정렬된다. 쉽게 이야기해서 heap pop을 수행한 뒤, 그 값을 배열의 가장 마지막부터 저장하는것과 크게 차이가 없다. (Max Heap의 경우)
heapify()
함수 하나로 build heap, Push, Pop, Sort 까지 너무나도 쉽게 구현을 할수 있다. 이 얼마나 은혜로운 코드인가 ㅜㅜ
void heap_sort(int arr[])
{
build_heap(arr, heap_size);
for (int last_idx = heap_size - 1; last_idx >= 0; last_idx--) {
swap(arr, 0, last_idx);
heapify(arr, 0, last_idx);
}
}
main() 함수
상단 초기화 코드
#include <stdio.h>
#define ARR_SIZE 10
int arr[ARR_SIZE] = {4,1,5,7,10,9,2,3,8,6};
int arr2[2] = {3,7};
int heap_size;
void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
main() 함수
void print_arr(int arr[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main(int argc, char *argv[])
{
heap_size = ARR_SIZE;
/* heapify */
print_arr(arr, heap_size);
build_heap(arr, heap_size);
print_arr(arr, heap_size);
/* heap pop */
printf("(%d)\n", heap_pop(arr));
print_arr(arr, heap_size);
printf("(%d)\n", heap_pop(arr));
print_arr(arr, heap_size);
/* heap push */
heap_push(arr, 11);
print_arr(arr, heap_size);
heap_push(arr, 12);
print_arr(arr, heap_size);
heap_push(arr, 9);
print_arr(arr, heap_size);
heap_push(arr, 10);
print_arr(arr, heap_size);
/* heap sort */
heap_sort(arr);
print_arr(arr, heap_size);
return 0;
}
References
- heapify sift down 재귀함수 참고 https://www.programiz.com/dsa/heap-sort
- heapify 동작을 이해하기 쉽게 설명 (영상)https://youtu.be/JBHCJA2B_ss
- Heap의 sift up과 sift down 에 대해서
https://leeminju531.tistory.com/33
Author And Source
이 문제에 관하여([C] 우선순위 큐(Heap) 및 Heap Sort 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soopsaram/우선순위-큐-heap-구현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)