查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

/* 如果待插入的值比当前已有的最大值小，则用这个数替换替换当前已有的最大值；

*  如果带插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，

*  因为我们容器内已经有k个数字比它小了，于是我们可以抛弃这个整数。

*/

#include <set>
#include <vector>
#include <iostream>

using namespace std;

typedef multiset<int, greater<int> > IntHeap;

void findKLeastNumbers( const vector<int>& data,
                        IntHeap& leastNumbers,  // output
                        unsigned int k )
{
    leastNumbers.clear();

    if(0 == k || data.size() < k)
        return;

    vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++iter)
    {
        // less than k numbers was inserted into leastNumbers
        if(leastNumbers.size() < k)
            leastNumbers.insert(*iter);
        else
        {
            // first number in leastNumbers is the greatest one
            IntHeap::iterator iterFirst = leastNumbers.begin();

            // if is less than the previous greatest
            if( *iter < *(leastNumbers.begin()) )
            {
                //replace the previous greatest number
                leastNumbers.erase(iterFirst);
                leastNumbers.insert(*iter);
            }
        }
    }
}

// www.cnblogs.com/aLittleBitCool/archive/2011/01/18/1938733.html

// www.cnblogs.com/mingzi/archive/2009/08/04/1538448.html