C++に挿入するたびにK番目に小さい要素

このチュートリアルでは、 k-thを見つけます。 挿入するたびに最小の要素。

最小ヒープを使用して問題を解決します。プログラムを完了するための手順を見てみましょう。

• ランダムデータでアレイを初期化します。
• 優先キューを初期化します。
• 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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。