#pragma once
#include <iostream>
using namespace std;


const int SIZE = 20;
class Heap {
private:
  int arr[SIZE];
  int n;

  void heapUp(int child);
  void heapDown(int parent);
  //convenience
  int left(int i) { return 2 * i + 1; }
  int right(int i) { return 2 * i + 2; }
  int parent(int i) { return (i - 1) / 2; }

public:
  Heap(void);
  ~Heap(void);

  void insert(int value);
  int remove();
  void print();
  void sort();
};



#include "Heap.h"

Heap::Heap(void) { n = 0; }
Heap::~Heap(void) {}
void Heap::insert(int value) {
  if (n == SIZE)
    exit(1);
  arr[n] = value;
  heapUp(n++);
}
void Heap::heapUp(int i) {
  int p = parent(i);
  if (arr[i] > arr[p]) {
    swap(arr[i], arr[p]);
    heapUp(p);
  }
}
int Heap::remove() {
  if (n == 0)
    exit(1);
  int temp = arr[0];
  arr[0] = arr[--n];
  heapDown(0);
  arr[n] = 0;
  return temp;
}
void Heap::heapDown(int i) {
  int l = left(i);
  int r = right(i);
  // comparing parent to left/right child
  // each has an inner if to handle if the first swap causes a second swap
  //  ie    1   ->   3   ->   5
  //      3   5    1   5    1   3
  if (l < n && arr[i] < arr[l]) {
    swap(arr[i], arr[l]);
    heapDown(l);
    if (r < n && arr[i] < arr[r]) {
      swap(arr[i], arr[r]);
      heapDown(r);
    }
  } else if (r < n && arr[i] < arr[r]) {
    swap(arr[i], arr[r]);
    heapDown(r);
    if (l < n && arr[i] < arr[l]) {
      swap(arr[i], arr[l]);
      heapDown(l);
    }
  }
}
void Heap::print() {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
// adding a print inside since the sort itself destroys size incrementor
void Heap::sort() {
  int temp = n;
  while (n > 1) {
    swap(arr[--n], arr[0]);
    heapDown(0);
  }
  for (int i = 0; i < temp; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}