Read n numbers and k. Print the k smallest numbers in increasing order. Use a min-heap: push all n numbers, then pop k times.
What to build
A min-heap in an array, used to pick out the smallest numbers.
Requirements
- Push every number, sifting it up.
- Pop
ktimes, sifting the new root down each time. - Print the popped numbers in the order they come out.
Input
The first line has n and k (1 ≤ k ≤ n ≤ 1000). The second line has the n numbers.
Output
The k smallest numbers in increasing order, separated by spaces.
Constraints
1 ≤ k ≤ n ≤ 1000.
Example
Input:
6 3
40 10 30 5 20 10
Output:
5 10 10
Why it works
The smallest number is always at the root of a min-heap. Each pop removes it and repairs the heap, so the next smallest rises to the root.
Examples
Example 1 · Input
6 3 40 10 30 5 20 10
Expected output
5 10 10
Example 2 · Input
1 1 -4
Expected output
-4
Hints
Hint 1
Push every number into a min-heap stored in an array: add at the end, then sift up.
Hint 2
Pop k times: take heap[0], move the last item to the root, then sift down.
Hint 3
Each pop gives the next smallest number.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int heap[1000];
int size = 0;
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void push(int x) {
int i = size++;
heap[i] = x;
while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
swap(&heap[(i - 1) / 2], &heap[i]);
i = (i - 1) / 2;
}
}
int pop(void) {
int top = heap[0];
heap[0] = heap[--size];
int i = 0;
while (1) {
int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
if (l < size && heap[l] < heap[smallest]) smallest = l;
if (r < size && heap[r] < heap[smallest]) smallest = r;
if (smallest == i) break;
swap(&heap[i], &heap[smallest]);
i = smallest;
}
return top;
}
int main(void) {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
push(x);
}
for (int i = 0; i < k; i++) {
if (i > 0) printf(" ");
printf("%d", pop());
}
printf("\n");
return 0;
}