use templates. be complete for any class to use this a? After rray you implement

Question

 use templates.

be complete for any class to use this a? After rray you implement, create a
“links”  operator forostream.
 Then show the index after inserting: 345790

Explanation / Answer

Dear Giving you class Heap-max class using templates #ifndef HEAP_H #define HEAP_H #include #include #include #include template class MaxHeap { private: std::vector heap; int parent(int i) {return (i - 1) / 2;} // returns index of parent (no bounds checking) int left(int i) {return 2 * i + 1;} // index of left child (no bounds checking) int right(int i) {return 2 * i + 2;} // index of right child (no bounds checking) /** under the assumption (!!) that the portions of heap rooted at left(i) and right(i) are max-heaps makes the portion of heap rooted at i into a max heap */ void max_heapify(int i); void build_max_heap(); /** used for inserting new elements allows key to float up through the heap as necessary @param i index at which heap will initially be overwritten with element key @param key value of element to insert at index i the idea is that i will NOT be the final index of key but key will be moved up appropriately when key >= heap.at(i) */ void heap_increase_key(int i, T key) throw(std::invalid_argument); // needed for max_heap_insert() public: // default constructor just uses vector default constructor (heap is empty) MaxHeap() {} // constructor from vector MaxHeap(std::vector v); // constructor from array MaxHeap(T arr[], size_t size); // accessor const T at(int i); void show(); MaxHeap& operator=(const MaxHeap&); /** note that to get a sorted copy of an arbitrary vector, this implementation requires 2 steps: 1) use your vector to contruct a heap 2) run the heap_sort() method WARNING! this method clears also clears the contents of heap heap will be empty after this method has run I implemented it this way in order to optimize the class for sorting even large inputs (other option would be making a copy of heap) @return vector vector is a sorted version of heap */ std::vector heap_sort(); T heap_maximum() throw(std::underflow_error); // Cormen et al., p. 163 T heap_extract_max() throw(std::underflow_error); // Cormen et al., p. 163 void max_heap_insert(const T key); }; // constructor from vector template MaxHeap::MaxHeap(std::vector v) { heap = v; build_max_heap(); } // constructor from array template MaxHeap::MaxHeap(T arr[], size_t size) { std::vector v(arr, arr + size); heap = v; build_max_heap(); } template void MaxHeap::max_heapify(int i) { int left = MaxHeap::left(i), right = MaxHeap::right(i), largest; size_t heap_size = heap.size(); if (left heap.at(i)) largest = left; else largest = i; if (right heap.at(largest)) largest = right; if (largest != i) { std::swap(heap.at(i), heap.at(largest)); max_heapify(largest); } } template void MaxHeap::build_max_heap() { size_t size = heap.size(); for (int i = size / 2 - 1; i >= 0; --i) { max_heapify(i); } } template const T MaxHeap::at(int i) { return heap.at(i); // exception will be thrown if i is out of range } template void MaxHeap::show() { size_t size = heap.size(); int i; std::cout 0) { for (i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.