//based on:https://www.geeksforgeeks.org/binary-heap/ but redone with resizing, template for any objects class, and full garbage management ////////////////////////////////////////// // Maximum Heap Template (heap of objects) ////////////////////////////////////////// // Paul Caron ///////////////////////////////////////// #include #include #include using namespace std; template class maxHeap{ private: int size=0; T* arr; int capacity; public: maxHeap(int capacity){ arr=new T[capacity]; this->capacity = capacity ; } ~maxHeap(){ delete[] arr; } void add(T& data){ if(size>=capacity){ resize(); } int index = size; size++; arr[index] = data; while(index!=0&&arr[index]>arr[parent(index)]){ swap(index,parent(index)); index=parent(index); } } T extractMax(){ if (size <= 0) { return T(NULL); //return Null object } if (size == 1){ size--; return arr[0]; } // Store the minimum value, and remove it from heap T root = arr[0]; arr[0] = arr[size-1]; size--; MaxHeapify(0);//sort the heap at index 0; return root; } void MaxHeapify(int i){//sort int l = left(i); int r = right(i); int biggest = i; if (l < size && arr[l] > arr[i]) biggest = l; if (r < size && arr[r] > arr[biggest]) biggest = r; if (biggest != i){ swap(i, biggest); MaxHeapify(biggest); } } //secondary functions void resize(){ cout<<"\n(resizing from "<parent:"<value=value; // cout<<"x"; } Object(const Object& o){ // cout<<"a"; this->value=o.value; } ~Object(){ // cout<<"*" ; }//overloading the < operator for heap sorting bool operator> (const Object& o2){ if(this->value>o2.value)return true; return false; } }; int main() { maxHeap

Max Heap Template