get minimum k numbers in array

get_min_k_numbers.cpp

// key idea: use max heap not min heap!!!! And the max heap is declared using less<int> for priority_queue
// maybe confusing
// time: build heap O(k), scan the rest n-k numbers takes O((n-k)logk),
// so, overall, time is O(nlogk), space is k.

// idea 2: use quick selection algorithm

vector<int> get_min_k_numbers(vector<int> &A, int k) {
	if(k >= A.size()) return A;
	vector<int> res;
	if(A.empty() || k == 0) return res;
	// should be less<int>, q is a max heap
	priority_queue<int, vector<int>, less<int>> q; 
	for(int i=0; i<A.size(); i++) {
		if(i < k) q.push(A[i]);
		else {
			int t = q.top();
			if(A[i] < t) {
				q.pop();
				q.push(A[i]);
			}
		}
	}
	while(!q.empty()) {
		res.push_back(q.top());
		q.pop();
	}
	return res;
}