資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝設計學
法律研究查詢序列中第 k 大元素的 C++ 程式
在這個程式中，我們需要提取序列中的第 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
更新於： 30-07-2019
235 次瀏覽
廣告