Given n numbers, find out the least k numbers from them

I have been solving the following problem:


Given n numbers find out the least k numbers from them. For example, if there are 8 numbers like 5,6,3,4,7,8,9,-1. For k = 3 the result will be -1,3,4.

I implemented it in the following way:

• make heap with first k numbers

• traverse the rest k-n numbers

• if heapMax > any of the k numbers then

• swap

• return heap containing k numbers

Can you please review my code and provide me with feedback?

#include 
#include 
#include 

std::vector getKLeastNumbers(std::vector &nums, int k)
{
    std::vector tmpNums;

    if(k nums.size())
    {
        return tmpNums;
    }

    for(int i=0; i nums.at(i))
        {
            int tmp = nums.at(i);

            nums.at(i) = tmpNums.front();

            std::pop_heap(tmpNums.begin(),tmpNums.end());
            tmpNums.pop_back();

            tmpNums.push_back(tmp);
            std::push_heap(tmpNums.begin(), tmpNums.end());
        }
    }

    return tmpNums;
}

int main()
{
    // test codes
    std::vectornums;
    nums.push_back(56);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(60);
    nums.push_back(-6);
    nums.push_back(3);
    nums.push_back(600);

    nums = getKLeastNumbers(nums,1);

    for(int i=0; inums2;
    nums2.push_back(56);

    nums2 = getKLeastNumbers(nums2,-1);

    std::cout<<std::endl<<"Test set 2 "<<std::endl;
    for(int i=0; i<nums2.size(); i++)
    {
        std::cout<<nums2.at(i)<<std::endl;
    }
}

I assume you can use C++11.

-
Use initializer lists:

std::vectornums;
nums.push_back(56);
nums.push_back(5);
nums.push_back(6);
nums.push_back(60);
nums.push_back(-6);
nums.push_back(3);
nums.push_back(600);

becomes

std::vector nums = {56, 5, 6, 60, -6, 3, 600};

-
Use range based for:

nums = getKLeastNumbers(nums, 1);

for(int i=0; i<nums.size(); i++)
{
    std::cout<<nums.at(i)<<std::endl;
}

becomes

for (auto &i : getKLeastNumbers(nums, 1))
    std::cout << i << '\n';

-
Do not hide bugs. If you detect that someone used your function wrong tell them instead of letting them wonder why the return value doesn't make sense.

if(k nums.size())
{
    return tmpNums;
}

becomes

assert(k  nums.size());

or

if (k  nums.size())
    throw std::range_error("k must be bigger than 0 and less than num's size");

-
You seem to be using the heap functions correctly, however, there are functions more suitable for that. I would pick std::partial_sort.

std::vector getKLeastNumbers(std::vector &nums, int k)
{
    std::partial_sort(std::begin(nums), std::begin(nums) + k, std::end(nums));
    return { std::begin(nums), std::begin(nums) + k };
}

-
The declaration for getKLeastNumbers is a bit strange. nums is not const and gets modified which feels unexpected. Why can I not use getKLeastNumbers on a const std::vector?. I would prefer a const & to preserve the original value, allow const vector and to be able to initialize nums with an initializer list directly.

StackExchange Code Review Q#70027, answer score: 8