C++의 최대 힙에서 K번째 가장 큰 요소

이 튜토리얼에서는 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>> 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>{ 44, 42, 35, 33, 31, 19, 27, 10, 26, 14 };
   cout << findKthGreatestElement(heap, 4) << endl;
   return 0;
}

출력

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

33

결론

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