C ++程序查找序列中的第k个最大元素
在此程序中,我们需要从序列中提取第K个最大元素。通过使用最大堆来解决该问题,可以提高该技术的时间复杂度。该程序的时间复杂度为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
热门推荐
2 成都训练狗狗
3 怎么训练小狗狗
4 训练狗狗软件
5 如何训练狗狗拉屎
9 狗狗负重训练
10 狗狗多大可以训练大小便
11 怎么训练狗狗萨摩耶
12 狗狗训练书
13 鞍山狗狗训练
14 训练狗狗用品
15 怎样才能训练狗狗听话
16 狗狗如何训练大小便
17 怎样训练狗狗睡狗窝
18 训练狗狗工具