#include <iostream>
using namespace std;
template <class T>
class MinHeap {
public:
MinHeap(const int size=20) {
maxSize=(size>0)?size:20;
currentSize=0;
array = new T[maxSize];
}
MinHeap(const T a[], int n, int msize) {
if (n <= 0) {cout << "empty!" << endl; return;}
maxSize = msize;
array = new T[maxSize];
currentSize = n;
for (int i = 0; i < currentSize; i++ ) {array[i] = a[i];}
buildHeap();
}
~MinHeap() { delete [] array;}
void insert(const T &);
void deleteTop();
void printAll() const {
for(int i = 0; i < currentSize; i++) {
cout << array[i] << " ";
} cout << endl;
}
void buildHeap() {
for (int i = currentSize/2-1; i >= 0; i--) {
filterDown(i);
}
}
private:
int maxSize, currentSize;
T *array;
void filterDown(int);
void filterUp(int);
int leftChild(int) const;
int parent(const int &) const;
void swap(const int &, const int &);
};
template <class T>
void MinHeap<T>::insert(const T &data) {
if (currentSize == maxSize) {
cout << "The heap is full!" << endl;
return;
}
array[currentSize] = data;
filterUp(currentSize);
currentSize++;
}
template <class T>
void MinHeap<T>::filterUp(int pos) {
int par = parent(pos);