우선순위 큐에 대하여 배워보았으니 이제 우선순위 큐를 어디에 사용하고 어떻게 응용하는 지에 대하여 알아보겠습니다. 힙 정렬(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 ..

우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출(FIFO)기반의 자료구조로 알려져있는데 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가게 됩니다. (ex. 구급차, 소방차가 다른 차들보다 먼저 나가는 일) 우선순위 큐의 종류에는 최소 우선순위 큐와 최대 우선순위 큐가 있으며 구현방법에는 배열, 연결리스트, 히프(heap)가 있습니다. 우선순위 큐의 구현방법 - 배열 우선 순위큐는 완전 이진 트리이므로 각 노드에 순서대로 번호를 붙일 수 있습니다. 붙여진 번호가 배열의 인덱스인 것입니다. 배열을 이용하여 트리를 구현하는 방법과 동일합니다. 배열을 이용하면 다음과 같은 규칙에 의해서 부모노드와 자식노드를 찾기가 쉽습니다. - 왼..