【C++】最大ヒープを使ってシーケンス内のk番目に大きい要素を検索するプログラム

このプログラムでは、数列（シーケンス）の中からk番目に大きい要素を取り出す方法を解説します。単純なソートを用いる代わりに最大ヒープ（max-heap）を利用することで、処理時間を大幅に短縮できます。

本プログラムの計算量は O(n + k*log(n)) です。ヒープの構築に O(n)、k回の最大値抽出と再ヒープ化にそれぞれ O(log n) かかるためです。

アルゴリズム

開始
　　ヒープの最大値をシーケンスの末尾に移動する
　　残りのシーケンスを再度ヒープ化（heapify）する
　　この処理を「k」回繰り返す
　　配列の最終状態を出力する
　　k回目の反復でヒープから取り出された最大値を結果として出力する
終了

サンプルコード

#include <iostream>
using namespace std;
void MaxHeapify(int a[], int i, int n) {
    int j, t;
    t = a[i];
    j = 2*i;
    while (j <= n) {
       if (j < n && a[j+1] > a[j])
       j = j+1;
       if (t > a[j])
       break;
       else if (t <= a[j]) {
          a[j/2] = a[j];
          j = 2*j;
       }
    }
    a[j/2] = t;
    return;
}
void Build_MaxHeapify(int a[], int n) {
    int i;
    for(i = n/2; i >= 1; i--)
    MaxHeapify(a, i, n);
}
int main() {
    int n, i, temp, k;
      cout<<"\nEnter the number of data element to be sorted: ";
      cin>>n;
      n++;
      int arr[n];
      for(i = 1; i < n; i++) {
         cout<<"Enter element "<<i<<": ";
         cin>>arr[i];
      }
      cout<<"\nEnter the k value: ";
      cin>>k;
      Build_MaxHeapify(arr, n-1);
      for(i = n-1; i >= n-k; i--) {
        temp = arr[i];
        arr[i] = arr[1];
        arr[1] = temp;
        MaxHeapify(arr, 1, i - 1);
      }
      cout<<"\nAfter max-heapify the given array "<<k<<" times the array state is: ";
     for(i = 1; i < n; i++)
       cout<<"->"<<arr[i];
     cout<<"\n\nThe "<<k<<"th largest element is: "<<arr[n-k];
     return 0;
}

実行例

Enter the number of data element to be sorted: 5
Enter element 1: 20
Enter element 2: 10
Enter element 3: 30
Enter element 4: 70
Enter element 5: 60
Enter the k value: 2
After max-heapify the given array 2 times the array state is: ->30->20->10->60->70
The 2th largest element is: 60

コードのポイント

MaxHeapify関数は、指定したノードを起点として、親子関係の大小比較を行いながら部分木をヒープ条件に沿うよう再構成します。Build_MaxHeapify関数は、配列の後半（葉に近いノード）から順にMaxHeapifyを適用することで、配列全体を最大ヒープへと変換します。

main関数では、まず入力データで最大ヒープを構築し、その後「ヒープの先頭（最大値）を末尾と交換 → ヒープサイズを縮めて再ヒープ化」という手順をk回繰り返します。これにより、配列の末尾側に大きい順でk個の要素が並び、arr[n-k] の位置にk番目に大きい要素が格納されます。