Data Structure - HEAP

#include <iostream>

using namespace std;

#define SWAP(a, b) { int temp = a; a = b; b = temp; }

struct heap {
  int tree[40001];
  int idx;

  void init() {
    idx = 0;
  }

  int size() {
    return idx;
  }

  bool empty() {
    return !idx;
  }

  int top() {
    return tree[1];
  }

  // Push & Pop
  void push(const int data) {
    tree[++idx] = data;

    for (int i = idx; i > 0; i /= 2) {
      if (i / 2 != 0 && tree[i / 2] < tree[i]) {
        swap(tree[i / 2], tree[i]);
      }
    }
  }

  void pop() {
    if (empty()) {
      return;
    }

    tree[1] = tree[idx--];
    for (int i = 1; i * 2 <= idx;) {
      int k = i * 2 + 1;
      if (i * 2 == idx || tree[i * 2 + 1] < tree[i * 2]) {
        k = i * 2;
      }

      if (tree[i] < tree[k]) {
        swap(tree[i], tree[k]);
        i = k;
      } else {
        break;
      }
    }
  }

  void print() {
    for (int i = 1; i <= idx; ++i) {
      cout << tree[i] << " ";
    }
    cout << '\n';
  }

  // Sort
  void heapify(int i, int n) {
    int largest = i;
    int left = i * 2;
    int right = i * 2 + 1;

    if (left < n && tree[left] > tree[largest]) {
      largest = left;
    }
    if (right < n && tree[right] > tree[largest]) {
      largest = right;
    }
    if (largest != i) {
      SWAP(tree[i], tree[largest]);
      heapify(largest, n);
    }
  }

  void buildHeap(int n) {
    for (int i = n / 2; i > 0; --i) {
      heapify(i, n);
    }
  }

  void heapSort(int n) {
    buildHeap(n);

    for (int i = n - 1; i > 0; --i) {
      SWAP(tree[i], tree[1]);
      heapify(i, n);
    }
  }
};

int main() {
  heap h;

  h.init();
  h.push(100);
  h.push(59);
  h.push(3000);
  h.push(500);
  h.push(1);
  h.print();

  h.heapSort(h.size());
  h.print();

  h.pop();
  h.pop();
  h.pop();
  h.print();

  return 0;
}