You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
36 lines
751 B
36 lines
751 B
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 1e5 + 10;
|
|
int n, m;
|
|
int sz;
|
|
int heap[N];
|
|
void down(int u) {
|
|
int t = u;
|
|
if (u * 2 <= sz && heap[u * 2] < heap[t])t = u * 2;
|
|
if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t])t = u * 2 + 1;
|
|
if (u != t) {
|
|
swap(heap[u], heap[t]);
|
|
down(t);
|
|
}
|
|
}
|
|
void up(int u) {
|
|
while (u / 2 && heap[u / 2] > heap[u]) {
|
|
swap(heap[u / 2], heap[u]);
|
|
u /= 2;
|
|
}
|
|
}
|
|
int main() {
|
|
cin >> n >> m;
|
|
for (int i = 1; i <= n; i++) cin >> heap[i];
|
|
|
|
sz = n;
|
|
for (int i = n / 2; i >= 1; i--) down(i);
|
|
|
|
while (m--) {
|
|
printf("%d ", heap[1]);
|
|
heap[1] = heap[sz--];
|
|
down(1);
|
|
}
|
|
return 0;
|
|
} |