template<typename dtype> class heap { public: /** TO DO:: default constructor perform new to reserve memory of size INITIAL_CAPACITY. set num_items = 0; */ heap() { // write your code here }; /** Create a heap from a given array */ heap(dtype *other, size_t len) { // write your code here }; /** copy constructor copy another heap to this heap. */ heap(const heap &other) { //write your code here }; /** Accessor functions */ /** returns the root of the heap */ dtype &root(); /** returns the left child of the given node. */ size_t left(size_t index); /** returns the right child of the given node. */ size_t right(size_t index); /** returns the parent of the given node. */ size_t parent(size_t index); /** returns num_items of the array */ size_t size(); /** Core heap operations */ /** perform heapify operation over the array. */ void heapify(size_t index); /** create a heap from the given input. */ void build_heap(); /** heap sort create a copy darray to sorted_array. then perform heapsort over sorted_array. */ void heapsort(); /* insert items into heap */ void insert(const dtype &key); /* remove items from the heap*/ void remove(); /** print heap **/ void print(std::string name); private: static const size_t INITIAL_CAPACITY; size_t num_items; dtype *darray; dtype *sorted_array; }; //end of class heap template<typename dtype> const size_t heap::INITIAL_CAPACITY = 100; } } #endif