寻找上亿数据TOP K
// [10/10/2013 qingezha]寻找上亿数据TOP Kvoid FindKMax()
{
//for(long i=0;i<1000;i++)
//{
// ofstream outFile; //输出到外存
// outFile.open("D:\\t.txt",ios_base::app);
// srand(i);
// long s=rand()<<6;
// outFile<<s<<" ";
// outFile.close();
//}
//
//system("pause");
// 定义数组存储堆元素
int k;
cin >> k;
long *heap = new long [k+1]; //注，只需申请存储k个数的数组
FILE *fp = fopen("D:\\t.txt", "r"); //从文件导入海量数据（便于测试，只截取了9M的数据大小）
assert(fp);
for (int i = 1; i <= k; i++)
fscanf(fp, "%d ", &heap[i]);
for (int j = 1; j <= k; j++)
cout << heap[j] << " ";
cout << endl;
for (int i=k/2+1;i>=1;--i)
{
siftMaxx(heap,i,k);
}
for (int j = 1; j <= k; j++)
cout << heap[j] << " ";
cout << endl;
long newData;
while (fscanf(fp, "%d", &newData) != EOF)
{
if (newData > heap[1]) //找最小的K个数 如果遇到比堆顶元素kmax更小的，则更新大堆,
{ //找最大的K数，更新小堆
heap[1] = newData;
siftMaxx(heap,1,k); //调整堆
for (int j = 1; j <= k; j++)
cout << heap[j] << " ";
cout << endl;
}
}
for (int j = 1; j <= k; j++)
cout << heap[j] << " ";
cout << endl;
fclose(fp);
system("pause");
}
void siftMaxx( long arr[],int low,int high ) /*区间[low,high],构造二叉堆//大的到根部去，小的到叶子去*/
{
// 这两中方法都可以 ,但是推荐第二种
int i=low;
int j=2*i;
int temp=arr[i];
while(j<=high)
{
if (j<high&&arr[j]>arr[j+1])
j++;
if (arr[i]>arr[j])
{
arr[i]=arr[j];
i=j;
j=2*i;
}
else break;
arr[i]=temp;
}
//////////////////////////////////////////////////////////////////////////
int child;
for (int i=1;i<high;i=child)
{
child=2*i;
if (child+1<=high&&arr[child]>arr[child+1])
++child;
if(arr[child]<arr[i]) //检查是否越界，很多时候的bug最后检查出来都是小毛病，但是浪费了很多时间
//if(child<=high&&arr[child]<arr[i]) 这样就对了
swap(arr[child],arr[i]);
}
}
ptr_has_space head[HASHLEN];//不能在头文件中定义
void write_to_file()//将hash后的结果保存在result.txt中
{
FILE *fp = fopen("D:\\result.txt", "w");
assert(fp);
int i = 0;
while (i < HASHLEN)
{
for (ptr_has_space p = head[i]; p != NULL; p = p->next)
fprintf(fp, "%d %d\n", p->data, p->count);
i++;
}
fclose(fp);
}
void append_hash( const int *p )//附加到hash表中，如果重叠则链表表示
{
int index=hash_function(p);
ptr_has_space q=head[index];
if(NULL==q)
{
head[index]=new node_has_space;
head[index]->count=1;
head[index]->data=*p;
head[index]->next=NULL;
return;
}
else
{
while(q)
{
if(*p==q->data)
{
++(q->count);
return;
}
q=q->next;
}
ptr_has_space pt=new node_has_space;
pt->count=1;pt->data=*p;
pt->next=head[index];//采用头插入法
head[index]=pt;
}
}
int hash_function( const int * p )//简单hash函数
{
int index=0;
if(*p>HASHLEN)
index=*p%HASHLEN;
else
index=*p;
return index;
}
void siftheap( node_has_space arr[],int low,int high )//堆结点类型为node_has_space，筛选
{
int i=low;
int j=2*i;
node_has_space temp=arr[i];
while(j<=high)
{
if (j<high&&arr[j].count>arr[j+1].count)
j++;
if (arr[i].count>arr[j].count)
{
arr[i]=arr[j];
i=j;
j=2*i;
}
else break;
arr[i]=temp;
}
}
void bigDATASearch()
{
//写进数据，模拟上亿的数据
//for(long i=0;i<100000;i++)
//{
// ofstream outFile; //输出到外存
// outFile.open("D:\\t.txt",ios_base::app);
// srand(i);
// long s=rand()%30000;
// outFile<<s<<" ";
// outFile.close();
//}
//
//system("pause");
//将上亿的数据归类，hash，记录重复的次数，然后以<key count> \n 形式写进txt里面
//int *dataptr=new int;
//FILE *fp = fopen("D:\\t.txt", "r"); //从文件导入海量数据
//assert(fp);
//while(fscanf(fp,"%d",dataptr)!=EOF)
//{
// append_hash(dataptr);
//}
//fclose(fp);
//write_to_file();
//system("pause");
//读取上述txt，用堆的形式取前K个count最大值
int k;
cin >> k;
ptr_has_space heap = new node_has_space[k+1]; //注，只需申请存储k个数的数组
FILE *fp = fopen("D:\\result.txt", "r"); //从文件导入海量数据（便于测试，只截取了9M的数据大小）
assert(fp);
&
补充：综合编程 , 其他综合 ,
