k_select.cpp

在若干个比较大的数字中找到k 个最大的数字－－－－K_select算法的实现与应用例子

///    梁剑（SG05225007）
////实验描述：Design a program to find k longest itemsets in a database of N records.
// Time is 5.6 
#include <conio.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream.h>
#define MAXV 10000


void sift(int r[],int low,int high)
{
	int i=low,j=2*i,temp=r[i];
	while(j<=high){
		if(j<high&&r[j]<r[j+1])j++;
		if(temp<r[j]){
			r[i]=r[j];
			i=j;
			j=2*i;
		}
		else break;
	}
	r[i]=temp;
}

void heap1(int r[],int n,int k)
{
	int i,temp;
	for(i=n/2;i>=0;i--)
		sift(r,i,n);
	for(i=n;i>=n-k;i--){
		temp=r[0];
		r[0]=r[i];
		r[i]=temp;
		sift(r,0,i-1);
	}
}

int heap2(int r[],int n,int v)
{
	int i,temp,count=0;
	for(i=n/2;i>=0;i--)
		sift(r,i,n);
	for(i=n;i>=0;i--){
		if(r[0]<v)break;
		count++;
		temp=r[0];
		r[0]=r[i];
		r[i]=temp;
		sift(r,0,i-1);
	}
	return count;
}

void prod_data()
{
	FILE *fp;
	int i,a[MAXV];
	srand((unsigned)time(NULL));
	for(i=0;i<MAXV;i++)
		a[i]=rand()%40000+rand()%40000;
	fp=fopen("out.txt","w");
	for(i=0;i<MAXV;i++)
		fprintf(fp,"%d ",a[i]);
	fclose(fp);
}


void main()
{
	int a[MAXV],i,k,v,temp,count;
	FILE *fp;
	prod_data();
	fp=fopen("out.txt","r");
	for(i=0;i<MAXV;i++){
		fscanf(fp,"%d ",&temp);//read the file!
		a[i]=temp;
	}
	fclose(fp);
cout<<"*****************************************************************************";
cout<<endl<<endl<<"  Design a program to find k longest itemsets in a database of N records."<<endl<<endl;
printf("*****************************************************************************");
   char ch='y';
   while(ch=='y')
   {

	printf("                       Please input the value of k：");
	cin>>k;
	heap1(a,MAXV,k);//K
	fp=fopen("out1.txt","w");
	for(i=MAXV-1;i>=MAXV-k;i--){//write to the file
		fprintf(fp,"%d ",a[i]);
	}
	cout<<"the data has inputed the out1.txt successfully！\n";
	fclose(fp);
	cout<<" you want to continue？（Y/N）";
	cin>>ch;
   }
}