/** https://virtualuniversitystudies.blogspot.com/**/
#include <iostream>
#include <conio.h>
using namespace std;
class Heap {
public:
Heap(int capacity = 100);
void insert(const int &n);
void buildHeap(int* anArray, int n);
void perculateDown(int hole);
void printHeap(int size);
private:
int* array ;
int capacity;
int currentSize;
};
Heap::Heap(int capacity) {
array = new int[capacity + 1];
currentSize=0;
}
void Heap::insert(const int & x) {
int hole = ++currentSize;
for(; hole > 1 && x < array[hole/2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}
void Heap::buildHeap(int* Array, int n) {
for(int i = 1; i <= n; i++)
array[i] = Array[i-1];
currentSize = n;
for(int i = currentSize / 2; i > 0; i--)
perculateDown(i);
}
void Heap::perculateDown(int hole) {
int tmp = array[hole];
int child;
for(; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
if(child != currentSize && array[child+1] < array[child])
child++;
if(array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
return;
}
void Heap::printHeap(int size) {
for(int i=1; i<=size; i++) {
cout << array[i] << " ";
}
}
int main() {
int Array[] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};
Heap minHeap;
for(int i=0; i<17; i++) {
if(!(Array[i] % 2 == 0))
minHeap.insert(Array[i]);
}
cout << "Odd Min Heap using insert method: " << endl;
minHeap.printHeap(10);
minHeap.buildHeap(Array,16);
cout << "\nMin Heap using build method: " << endl;
minHeap.printHeap(16);
getch();
}
