এই প্রোগ্রামে, আমাদের একটি সিকোয়েন্স থেকে Kth সর্বাধিক উপাদান বের করতে হবে। এই সমস্যার সময় জটিলতা मैक्स-হিপ ব্যবহার করে উন্নত করা যায়। এই প্রোগ্রামের সময় জটিলতা O(n + k*log n)।
অ্যালগরিদম
শুরু হিপের সর্বাধিক মানকে সিকোয়েন্সের শেষে পাঠান। বাকি সিকোয়েন্সকে হিপিফাই করুন। প্রক্রিয়াটি 'k' বার दुহরান। অ্যারের চূড়ান্ত অবস্থা প্রিন্ট করুন। kth ইটারেশনে হিপ থেকে বের করা সর্বাধিক মান ফলাফল হিসেবে প্রিন্ট করুন। শেষ।
উদাহরণ কোড
#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 << "\nসর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: ";
cin >> n;
n++;
int arr[n];
for (i = 1; i < n; i++) {
cout << "এলিমেন্ট " << i << ": ";
cin >> arr[i];
}
cout << "\nk এর মান লিখুন: ";
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 << "\nঅ্যারে " << k << " বার ম্যাক্স-হিপিফাই করার পর অ্যারের অবস্থা: ";
for (i = 1; i < n; i++)
cout << "->" << arr[i];
cout << "\n\n" << k << "তম সর্বাধিক উপাদানটি হল: " << arr[n-k];
return 0;
}
আউটপুট
সর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: 5 এলিমেন্ট 1: 20 এলিমেন্ট 2: 10 এলিমেন্ট 3: 30 এলিমেন্ট 4: 70 এলিমেন্ট 5: 60 k এর মান লিখুন: 2 অ্যারে 2 বার ম্যাক্স-হিপিফাই করার পর অ্যারের অবস্থা: ->30->20->10->60->70 2তম সর্বাধিক উপাদানটি হল: 60
