1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#include <cstring> #include <iostream> #include <algorithm> #include <vector>
using namespace std;
void (vector<int> &heap, int size, int u) { int t = u, left = u * 2, right = u * 2 + 1; if (left <= size && heap[left] > heap[t]) t = left; if (right <= size && heap[right] > heap[t]) t = right; if (t != u) { swap(heap[u], heap[t]); push_down(heap, size, t); } }
void push_up(vector<int> &heap, int u) { while (u / 2 && heap[u / 2] < heap[u]) { swap(heap[u / 2], heap[u]); u /= 2; } }
void heap_sort(vector<int> &q, int n) { int size = n; for (int i = 1; i<=n; i++) push_up(q, i);
for (int i = 1; i<=n; i++) { swap(q[1], q[size]); size --; push_down(q, size, 1); } }
void insert(vector<int> &heap, int size, int x) { heap[ ++ size] = x; push_up(heap, x); }
void remove_top(vector<int> &heap, int &size) { heap[1] = heap[size]; size -- ; push_down(heap, size, 1); }
int main() { vector<int> q; int n; cin >> n; q.resize(n+1); for (int i = 1; i<=n; i++) cin >> q[i]; heap_sort(q, n); for (int i = 1; i<=n; i++) cout << q[i] << " " ; cout << endl; return 0; }
|
近期评论