#include #include

using namespace std;

#ifndef MINHEAP_H #define MINHEAP_H

template

class MinHeap { public: MinHeap(int capacity = 100) : Array(capacity + 1) , currentSize(0) {};

MinHeap(const vector & a) : Array(a.size() + 1) , currentSize (a.size()) { for (int i = 0; i < a.size(); i++) Array[i + 1] = a[i]; buildHeap(); }

bool isEmpty() const { return currentSize == 0; }

void insert(const T & item) { if (currentSize == Array.size() - 1) Array.resize(2 * Array.size());

int placeholder = ++currentSize;

while (placeholder > 1 && Array[placeholder / 2] > item) { Array[placeholder] = Array[placeholder / 2]; placeholder /= 2; } Array[placeholder] = item; }

void print() const { for (int i = 1; i <= currentSize; i++) cout << Array[i] << ' '; cout << endl; }

bool deleteMin() { if (isEmpty()) return false; Array[1] = Array[currentSize--]; percolateDown(1); return true; }

bool deleteMin(T & item) { if (isEmpty()) return false; item = Array[1]; Array[1] = Array[currentSize--]; percolateDown(1); return true; } private: vector Array; int currentSize;

void buildHeap() { for (int i = currentSize / 2; i >= 1; i--) percolateDown(i); }

void percolateDown(int placeholder) { T temp = Array[placeholder];

while (2 * placeholder <= currentSize) { int child = 2 * placeholder; if (child + 1 <= currentSize && Array[child + 1] < Array[child]) child++; if (temp > Array[child]) { Array[placeholder] = Array[child]; placeholder = child; } else break; } Array[placeholder] = temp; } };

#endif

Given the Minheap.h file provided to you, write a c++ program that takes N elements (choose N to be large; you can assume that elements are integers), and does the following: a) Inserts these elements in a minheap one by one (use insert function) b) Builds a minheap in linear time (use the Minheap constructor that takes a vector as argument) Compare the running time of both algorithms for: - sorted input - reverse-ordered input - random input