이 튜토리얼에서는 최소 힙(min-heap)에서 K번째로 작은 요소를 찾는 프로그램을 작성해 보겠습니다.
이 문제는 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 힙 전체를 정렬하지 않고도 원하는 값을 찾을 수 있는 방법으로, 프로그램 완성을 위한 단계를 하나씩 살펴보겠습니다.
문제 해결 단계
- 올바른 값으로 최소 힙을 초기화합니다.
- 우선순위 큐를 생성하고 최소 힙의 루트 노드를 삽입합니다.
- (k - 1)번 반복하는 루프를 작성합니다.
- 큐에서 가장 작은 요소를 꺼냅니다(pop).
- 꺼낸 노드의 왼쪽 자식과 오른쪽 자식 노드를 우선순위 큐에 추가합니다.
- 루프가 종료되면 우선순위 큐의 최상단(top) 요소가 바로 K번째로 작은 요소입니다.
- 해당 값을 반환합니다.
예제 코드
그럼 실제 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Heap {
vector<int> elemets;
int n;
Heap(int i = 0): n(i) {
elemets = vector<int>(n);
}
};
inline int leftIndex(int i) {
return 2 * i + 1;
}
inline int rightIndex(int i) {
return 2 * i + 2;
}
int findKthGreatestElement(Heap &heap, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>queue;
queue.push(make_pair(heap.elemets[0], 0));
for (int i = 0; i < k - 1; ++i) {
int node = queue.top().second;
queue.pop();
int left = leftIndex(node), right = rightIndex(node);
if (left < heap.n) {
queue.push(make_pair(heap.elemets[left], left));
}
if (right < heap.n) {
queue.push(make_pair(heap.elemets[right], right));
}
}
return queue.top().first;
}
int main() {
Heap heap(10);
heap.elemets = vector<int>{ 10, 14, 19, 24, 32, 41, 27, 44, 35, 33 };
cout << findKthGreatestElement(heap, 4) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
24
예제 힙의 요소를 오름차순으로 정렬하면 10, 14, 19, 24, 32, 33, 41, 44 순이 되므로, 네 번째로 작은 값인 24가 정확히 출력되는 것을 확인할 수 있습니다.
마무리
지금까지 우선순위 큐를 활용해 최소 힙에서 K번째 최솟값을 찾는 방법을 알아보았습니다. 이 접근 방식은 힙 구조의 특성을 그대로 활용하기 때문에 불필요한 정렬 없이도 원하는 값을 빠르게 찾을 수 있다는 장점이 있습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.