Binary Heap (Recursive)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int A[N<<1], n = 0;

void sift_down(int i) {
    if (i > n || (A[i] > A[2*i] && A[i] > A[2*i+1]))
        return;
    int p = (A[2*i] > A[2*i+1]) ? (2*i) : (2*i+1);
    swap(A[i], A[p]);
    sift_down(p);
}

void sift_up(int i) {
    if (i > 1 && A[i] > A[i/2]) {
        swap(A[i], A[i/2]);
        sift_up(i/2);
    }
}

void heapify() {
    for (int i = n/2; i >= 1; --i)
        sift_down(i);
}

void insert(int x) {
    A[++n] = x;
    sift_up(n);
}

int get_max() {
    return n == 0 ? -1 : A[1];
}

void extract_max() {
    if (n == 0)
        return;
    swap(A[n], A[1]);
    A[n--] = 0;
    sift_down(1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &A[i]);
    heapify();

    int k;
    scanf("%d", &k);
    while (--k)
        extract_max();
    printf("%d\n", get_max());

    return 0;
}