C++의 최소 힙에서 K'최소 요소

<시간/>

이 튜토리얼에서는 min-heap에서 k번째 최소 요소를 찾는 프로그램을 작성할 것입니다.

우리는 문제를 해결하기 위해 우선순위 큐를 사용할 것입니다. 프로그램을 완료하는 단계를 살펴보겠습니다.

정확한 값으로 최소 힙을 초기화합니다.
우선순위 큐를 생성하고 최소 힙의 루트 노드를 삽입합니다.
k - 1회 반복하는 루프를 작성합니다.
- 대기열에서 가장 작은 요소를 팝합니다.
- 위 노드의 왼쪽과 오른쪽 노드를 우선순위 큐에 추가합니다.
우선순위 큐의 가장 큰 요소는 이제 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;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.