Min-Heap Priority Queue
intro
Implement vector<int> pop_k(const vector<int>& a, int k) (vector<int> in C++, list of ints in Python, array of numbers in JavaScript). Push every element of a onto a min-heap, then pop k times, recording each popped value in order. In C++ the heap is built with priority_queue<int, vector<int>, greater<int>>; in Python, heapq is already a min-heap, so heappush/heappop need no comparator; JavaScript has no built-in heap or priority queue of any kind, so there the heap itself must be hand-rolled (sift-up on push, sift-down on pop). Assume 1 <= k <= a.size(), so the smallest value is popped first, then the next smallest, and so on. Return the recorded values as a vector of length k.
Example: pop_k({5, 3, 8, 1}, 3) returns {1, 3, 5}: the heap pops 1, 3, 5 in ascending order and stops after 3 pops, leaving 8 in the heap.
Input format: each test in tests/*.in is laid out as:
- Line 1:
n k, the array length and how many pops to perform. - Line 2: the
nvalues, space-separated.
Test 02.in reads:
1 1
7
This is a one-element array with k = 1: pop the only value, 7.
Where you'll use it:
✦ Solution & editorial unlock with the pass.