힙 정렬 (Heap Sort) 힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됩니다. 힙에는 최대 힙과 최소 힙이 존재합니다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리입니다. 힙 구조 생성과 최대 힙 연산에 관해서는 아래 포스팅에서 자세히 설명하였으니 참고하시기 바랍니다. https://yjg-lab.tistory.com/143?category=932096 [자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제 우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출..

우선순위 큐에 대하여 배워보았으니 이제 우선순위 큐를 어디에 사용하고 어떻게 응용하는 지에 대하여 알아보겠습니다. 힙 정렬(heap sort) 힙 정렬(heap sort)은 히프를 사용하는 정렬 알고리즘입니다. 먼저 정렬할 요소들을 최대 히프에 삽입하고 히프에서 하나씩 요소를 삭제하여 저장하면 정렬이 되는 방식입니다. 힙 정렬이 가장 유용한 경우는 가장 큰 값이 몇 개만 필요한 경우입니다. 힙 정렬 알고리즘 void heap_sort(element a[], int n) { int i; HeapType* h; h = create(); // 히프 생성 init(h); for (i = 0; i < n; i++) { insert_max_heap(h, a[i]); // 최대 히프로 삽입 } for (i = (n ..