# c++: Max Heap Template

https://en.wikipedia.org/wiki/Min-max_heap

My simple implementation of max heap.

Change the compare from > to < in below codes, you will get a min heap.

```
template<typename T>
class MaxHeap {
public:
MaxHeap() {
size_ = 0;
capacity_ = 2;
heap_ = new T[capacity_];
}
MaxHeap(int capacity) {
if (capacity >= 2) {
heap_ = new T[capacity];
capacity_ = capacity;
size_ = 0;
}
else {
size_ = 0;
capacity_ = 2;
heap_ = new T[capacity_];
}
}
~MaxHeap() {
if (heap_)
delete[] heap_;
}
public:
int size() { return size_; }
void insert(const T& t) {
if ((size_+1) >= capacity_) {
capacity_ *= 2;
T* tmp = new T[capacity_];
for (int i = 0; i <= size_; i++)
tmp[i] = heap_[i];
delete[] heap_;
heap_ = tmp;
}
size_++;
heap_[size_] = t;
int i = size_;
int tmp = heap_[i];
while (i > 1 && tmp > heap_[i / 2]) {
heap_[i] = heap_[i / 2];
heap_[i / 2] = tmp;
tmp = heap_[i / 2];
i /= 2;
}
heap_[i] = tmp;
}
T max() {
return heap_[1];
}
int index(const T& t) {
return index(1, t);
}
void removeByIndex(int i) {
if (i < 1)
return;
if (heap_[size_] == heap_[i]) {
heap_[i] = heap_[size_];
size_--;
return;
}
if (heap_[size_] < heap_[i]) {
heap_[i] = heap_[size_];
size_--;
maxDown(i);
return;
}
heap_[i] = heap_[size_];
size_--;
maxUp(i);
}
void remove(const T& t) {
return removeByIndex(index(t));
}
private:
inline int index(int i, const T& t) {
if (heap_[i] < t)
return -1;
if (heap_[i] == t)
return i;
int r = index(2 * i, t);
if (r != -1)
return r;
return index(2 * i + 1, t);
}
inline void maxDown(int i) {
if (i * 2 > size_ && (i * 2 + 1) > size_)
return;
int l = i * 2;
int r = l + 1;
int m = l;
if (r <= size_ && heap_[r] > heap_[l])
m = r;
if (heap_[m] <= heap_[i])
return;
T tmp = heap_[i];
heap_[i] = heap_[m];
heap_[m] = tmp;
maxDown(m);
}
inline void maxUp(int i) {
if (i <= 1)
return;
int p = i / 2;
if (heap_[p] >= heap_[i])
return;
T tmp = heap_[i];
heap_[i] = heap_[p];
heap_[p] = tmp;
maxUp(p);
}
private:
T* heap_;
int capacity_;
int size_;
};
```