# Untitled

unknown
plain_text
2 years ago
1.8 kB
2
Indexable
Never
```#include <iostream>
#include <vector>

using namespace std;

vector <int> heap;
int sz = 0;

int sift_up(int i) {
while (heap[i] > heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
return i;
}

int sift_down(int i) {
while (1) {
if (2 * i + 1 < sz  && 2 * i + 2 >= sz) {
if (heap[i] < heap[2 * i + 1]) {
swap(heap[i], heap[2 * i + 1]);
i = 2 * i + 1;
}
else {
return i;
}
}
else if (2 * i + 2 < sz) {
if (heap[2 * i + 2] > heap[2 * i + 1]) {
if (heap[2 * i + 2] > heap[i]) {
swap(heap[i], heap[2 * i + 2]);
i = 2 * i + 2;
}
else {
return i;
}
}
else {
if (heap[2 * i + 1] > heap[i]) {
swap(heap[i], heap[2 * i + 1]);
i = 2 * i + 1;
}
else {
return i;
}
}
}
else {
return i;
}
}
}

heap.push_back(x);
sz++;
return sift_up(heap.size() - 1);
}

int get_max() {
return heap[0];
}

pair <int, int> extract_max() {
if (sz == 0) {
return {-1, -1};
}
int mx = get_max();
swap(heap[0], heap[sz - 1]);
sz--;
int pos = sift_down(0);
return {pos, mx};
}

void build_heap(vector <int> &a) {
for (int i = 0; i < a.size(); i++) {
heap.push_back(a[i]);
sz++;
sift_up(i);
}
}

void build_heap2(vector <int> &a) {
for (int i = 0; i < a.size(); i++) {
heap.push_back(a[i]);
sz++;
}
for (int i = a.size() - 1; i >= 0; i--) {
sift_down(i);
}
}

int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
build_heap2(a);
for (int i = 0; i < n - 1; i++) {
extract_max();
}
for (int i = 0; i < n; i++)
cout << heap[i] << ' ';
}```