Problem Solving using C++

Algorithm Study using C++

partial_sort--基于堆排序

经常会出现求n个数中的前k个最小值(最大值),可以采取的策略为:

看n和k的大小,数组的规律。即便看情况也不一定有绝对的“最优"
如果是基本有序的,那么就用Hoare的算法,每次选中间位置的数当轴。
如果k或(n-k)是小常数,那么部分排序算法,比如用堆。
如果要抵抗算法复杂度攻击,那么可以考虑随机Hoare或者linear time selection.
在k为小值的时候,可以采用基于堆排序的部分排序方法:
代码如下:
#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;
    }
}


posted on 2007-08-27 22:49 Kingoal Lee's Alogrithm Study using cplusplus 阅读(308) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜