C++에서 삽입할 때마다 K번째로 작은 요소

이 튜토리얼에서는 k번째 삽입할 때마다 가장 작은 요소입니다.

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

• 임의의 데이터로 배열을 초기화합니다.
• 우선순위 대기열을 초기화합니다.
• k - 1까지 k번째가 없습니다. 가장 작은 요소. 따라서 원하는 기호를 인쇄하십시오.
• k + 1에서 n까지 반복하는 루프를 작성합니다.
  • 최소 힙의 루트를 인쇄합니다.
  • 요소가 최소 힙의 루트보다 크면 루트를 팝하고 요소를 삽입합니다.

예

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
void findKthSmallestElement(int elements[], int n, int k) {
   priority_queue<int, vector<int>, greater<int>> queue;
   for (int i= 0; i < k - 1; i++) {
      queue.push(elements[i]);
      cout << "- ";
   }
   queue.push(elements[k-1]);
   for (int i = k; i < n; i++) {
      cout << queue.top() << " ";
      if (elements[i] > queue.top()) {
         queue.pop();
         queue.push(elements[i]);
      }
   }
   cout << queue.top() << endl;
}
int main() {
   int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9};
   findKthSmallestElement(arr, 10, 5);
   return 0;
}

출력

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

- - - - 2 3 3 3 5 5

결론

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