rendered paste body#include <vector>#include <math.h>using namespace std;#ifndef HEAP_H#define HEAP_Htemplate<class T>class minHeap { public:void push(T);T pop();T top(){return Heap.front();};minHeap() { size = 0;}minHeap(T ar[],int sz) { size = 0; for (int i = 0 ; i < sz ; i++) push(ar[i]); buildminheap(); }void print(){ for (int i = 0 ; i < size ; i++) cout<<Heap[i]<<endl; }protected:private:vector<T> Heap; size_t size;int giveleft(int i) { return 2*i + 1; }int giveright(int i) { return 2*i + 2; }void Heapsort();void minHeapify(T);size_t giveparent(size_t);void buildminheap();}; template <class T>void swap(vector<T> A, int i, int j){ T temp = A[i]; A[i] = A[j]; A[j] = temp;}template<class T>void minHeap<T>::buildminheap(){for (int i = (size/2)-1; i >=0 ; i --) minHeapify(i);}template <class T>size_t minHeap<T>::giveparent(size_t index){ return (size_t(floor((index-1) / 2)));}template<class T>void minHeap<T>::minHeapify(T i){T l = giveleft(i);T r = giveright(i);T largest;if (l <=size-1 && Heap[l]<Heap[i]) largest = l; else largest = i;if (r <=size-1 && Heap[r]<Heap[largest]) largest = r;if (largest != i){ T temp = Heap[i]; Heap[i] = Heap[largest]; Heap[largest] = temp; minHeapify(largest);}}template<class T>void minHeap<T>::push(T item){Heap.push_back(item); for(size_t i=size; i>0 && (Heap[giveparent(i)] > Heap[i]); i = giveparent(i)) swap(Heap[giveparent(i)], Heap[i]);size++;}template<class T>T minHeap<T>::pop(){T temp = Heap[0];Heap[0] = Heap[size-1];size--;minHeapify(0);return(temp);} template<class T>void minHeap<T>::Heapsort(){buildminheap(); for (int i = size-1; i >= 1; i--) { T temp = Heap[0]; Heap[0] = Heap[i]; Heap[i] = temp; minHeapify(i-1); }} #endif