#include <iostream>
#include <vector>
#include <queue> // priority_queue
#include <algorithm> // qsort
std::vector<int> k_smallest_numbers(const std::vector<int>& vec, int k) {
if (k < 0) {
throw std::invalid_argument("k must be a non-negative integer");
}
if (k == 0 || vec.empty()) {
return {};
}
// Use a max-heap to keep track of the k smallest elements
std::priority_queue<int> max_heap;
for (int num : vec) {
if (max_heap.size() < k) {
max_heap.push(num);
} else if (num < max_heap.top()) {
max_heap.pop();
max_heap.push(num);
}
}
// Extract elements from the heap into a result vector
std::vector<int> result;
while (!max_heap.empty()) {
result.push_back(max_heap.top());
max_heap.pop();
}
std::sort(result.begin(), result.end());
return result;
}
int main() {
std::vector<int> vec = {42, 29, 90, 21, 90, 88, 37, 45};
int k = 3;
try {
std::vector<int> result = k_smallest_numbers(vec, k);
std::cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
std::cout << result[i];
if (i < result.size() - 1) std::cout << ", ";
}
std::cout << "]\n";
} catch (const std::exception& e) {
std::cerr << "Error: " << e.what() << "\n";
}
}
/*
run:
[21, 29, 37]
*/
