C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の最大ヒープでK番目に大きい要素


このチュートリアルでは、 k-thを見つけるプログラムを作成します。 最大ヒープからの最大の要素。

問題を解決するために優先キューを使用します。プログラムを完了するための手順を見てみましょう。

  • 正しい値で最大ヒープを初期化します。
  • 優先キューを作成し、最大ヒープのルートノードを挿入します。
  • 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

結論

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


  1. C++の最大ヒープの最小要素。

    問題の説明 最大ヒープの値が最小の要素を見つけます。 最大ヒープ以下を考えてみましょう。 ルートノードの最大ヒープ値は、常にその子ノードよりも大きくなります。このプロパティにより、値はリーフノードの1つに存在すると結論付けることができます。ヒープにn個のノードが含まれている場合、ceil(n / 2)リーフがあります。 最大ヒープは完全なバイナリツリーであるため、配列で表すことができます。このようなヒープでは、最初のリーフはfloor(n / 2)インデックスの後に存在します。したがって、この例では、最初の休暇はインデックス5に存在します。 アルゴリズム 以下のアルゴリズムを使

  2. ヒープソートを実装するC++プログラム

    ヒープは、最小ヒープまたは最大ヒープのいずれかである完全なバイナリツリーです。最大ヒープでは、ルートのキーは、ヒープに存在するすべてのキーの中で最大である必要があります。このプロパティは、そのバイナリツリー内のすべてのノードに対して再帰的に真である必要があります。最小ヒープは最小ヒープに似ています。 関数の説明 void BHeap ::Insert(int ele): 挿入操作を実行して、要素をヒープに挿入します。 void BHeap ::DeleteMin(): 削除操作を実行して、ヒープから最小値を削除します。 int BHeap ::ExtractMin(): ヒープから