T * values;

int capacity;

int sz;

binary_minheap(int capacity) : capacity(capacity), sz(0) {

values = (T*) calloc(capacity, sizeof(T));

}

~binary_minheap() {

delete values;

}

inline int parent(int i) { return (i+1)/2-1; }

inline int left(int i) { return i*2 + 1; }

inline int right(int i) { return i*2 + 2; }

inline void incrHeapSize() { sz++; assert(sz <= capacity); }

inline void decrHeapSize() { sz--; assert(sz >= 0); }

void insert(T element) {

incrHeapSize();

// percolate up

int pos = sz - 1; // http://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

for(; pos > 0 && element < values[parent(pos)]; pos=parent(pos))

values[pos] = values[parent(pos)];

values[pos] = element;

}

bool empty() { return sz == 0; }

void minHeapify(int i) {

int l = left(i);

int r = right(i);

int smallest;

if (l < sz && values[l] < values[i]) smallest = l;

else smallest = i;

if (r < sz && values[r] < values[smallest]) smallest = r;

if (smallest != i) {

// exchange

T tmp = values[i];

values[i] = values[smallest];

values[smallest] = tmp;

minHeapify(smallest);

}

}

T min() { return values[0]; }

void extractMin() {

values[0] = values[sz - 1];

decrHeapSize();

minHeapify(0);

}