鐪媙鍜宬鐨勫ぇ灝忥紝鏁扮粍鐨勮寰嬨傚嵆渚跨湅鎯呭喌涔熶笉涓瀹氭湁緇濆鐨?#8220;鏈浼?
濡傛灉鏄熀鏈湁搴忕殑錛岄偅涔堝氨鐢℉oare鐨勭畻娉曪紝姣忔閫変腑闂翠綅緗殑鏁板綋杞淬?br>濡傛灉k鎴?n-k)鏄皬甯告暟錛岄偅涔堥儴鍒嗘帓搴忕畻娉曪紝姣斿鐢ㄥ爢銆?br>濡傛灉瑕佹姷鎶楃畻娉曞鏉傚害鏀誨嚮錛岄偅涔堝彲浠ヨ冭檻闅忔満Hoare鎴栬卨inear
time selection.
鍦╧涓哄皬鍊肩殑鏃跺欙紝鍙互閲囩敤鍩轟簬鍫嗘帓搴忕殑閮ㄥ垎鎺掑簭鏂規硶錛?br>浠g爜濡備笅錛?br>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;
void min_heapify(int arr[],int i,int size)
{
int left = 2*i+1;
int right = left+1;
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
{
largest = i;
}
if((right<=size)&&(arr[right]>arr[largest]))
{
largest = right;
}
if(largest!=i)
{
int temp = arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
min_heapify(arr,largest,size);
}
}
void fillarray(int arr[],int size)
{
for(int i=0;i<size;i++)
{
arr[i]=rand()%size;
}
}
void print(const int arr[],int size)
{
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
}
int main(int argc,char* argv[])
{
int size,k;
while(cin>>size)
{
int* buff=new int[size];
fillarray(buff,size);
print(buff,size);
cout<<"Please input the top k value:"<<endl;
cin>>k;
for(int i=(k-1)/2;i>=0;i--)
min_heapify(buff,i,k-1);
print(buff,size);
cout<<endl<<endl;
for(int i=size-1;i>=k;i--)
{
if(buff[i]<buff[0])
{
int temp = buff[0];
buff[0]=buff[i];
buff[i]=temp;
min_heapify(buff,0,k-1);
}
}
print(buff,size);
delete [] buff;
}
}

]]>