시퀀스에서 k번째로 큰 요소를 찾는 C++ 프로그램

이 프로그램에서는 시퀀스에서 K번째로 큰 요소를 추출해야 합니다. 이 기술의 시간 복잡도는 max-heap을 사용하여 문제에 접근하여 개선할 수 있습니다. 이 프로그램의 시간 복잡도는 O(n + k*log(n))입니다.

알고리즘

Begin
   Send the max of the heap to the end of the sequence.
   Heapify the remaining sequence.
   Repeat the process for ‘k’ times.
   Print the final state of the array.
   Print the max from the heap extracted from kth iteration as a result.
End.

예시 코드

#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