इस प्रोग्राम में, हमें एक अनुक्रम से kवां सबसे बड़ा एलिमेंट निकालने की आवश्यकता है। इस समस्या को मैक्स-हीप का उपयोग करके हल करने पर समय जटिलता में सुधार किया जा सकता है। इस प्रोग्राम की समय जटिलता O(n + k*log n) है।
एल्गोरिदम
शुरुआत हीप के मैक्स को अनुक्रम के अंत में भेजें। शेष अनुक्रम को हीपिफाई करें। प्रक्रिया को '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<<"\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
