Manual Heap

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("text.in");
ofstream fout ("text.out");

struct PQ {
  int q[1 << 18], n;
};

inline void PQ_init (PQ *Q) {
  Q -> n = 0;
}

int Parent (int node) {
  if (node == 1)
    return -1;
  return node / 2;
}

inline int Left (int node) {
  return 2 * node;
}

inline int Right (int node) {
  return 2 * node + 1;
}

void Bubble_Up (PQ *Q, int p) {
  if (Parent(p) == -1)
    return;
  if (Q -> q[Parent(p)] > Q -> q[p]) {
    swap (Q -> q[Parent(p)], Q -> q[p]);
    Bubble_Up(Q, Parent(p));
  }
}

void Insert (PQ *Q, int x) {
  Q -> n ++;
  Q -> q[Q -> n] = x;
  Bubble_Up (Q, Q -> n);
}

void Make_Heap (PQ *Q, int a[], int n) {
  PQ_init(Q);
  for (int i = 0; i < n; i ++)
    Insert (Q, a[i]);
}

void Bubble_Down (PQ *Q, int p) {
  int st = Left (p),
      min_index = p;
  for (int i = 0; i < 2; i ++)
    if ((st + i) <= Q -> n)
      if (Q -> q[min_index] > Q -> q[st + i])
        min_index = st + i;
  if (min_index != p) {
    swap (Q -> q[min_index], Q -> q[p]);
    Bubble_Down (Q, min_index);
  }
}

int Min (PQ *Q) {
  int Min = Q -> q[1];
  Q -> q[1] = Q -> q[Q -> n];
  Q -> n --;
  Bubble_Down (Q, 1);
  return Min;
}

void HeapSort (int a[], int n) {
  PQ Q;
  Make_Heap(&Q, a, n);
  for (int i = 0; i < n; i ++)
    a[i] = Min (&Q);
}

int main () {
  int a[] = {1, 4, 7, 9, 2, 3, 6, 5, 1, 2, 3, 10}, n = 12;
  HeapSort(a, n);
  for (int i = 0; i < n; i ++)
    fout << a[i] << ' ';
  return 0;
}