Question

1 Approved Answer

Posted on Sep 07, 2024

Please add code for the function printGraph() so that the result looks like this. Please ONLY respond in C++. Additional helper functions is fine This

Please add code for the function printGraph() so that the result looks like this. Please ONLY respond in C++. Additional helper functions is fine image text in transcribed

This is the ArrayMaxHeap.cpp file:

// Created by Frank M. Carrano and Tim Henry. // Copyright (c) 2013 __Pearson Education__. All rights reserved. /** Array-based implementation of the ADT heap. @file ArrayMaxHeap.cpp */ #include  // for log2 #include  // #include  // #include "ArrayMaxHeap.h" #include "PrecondViolatedExcep.h" using namespace std; template int ArrayMaxHeap::getLeftChildIndex(const int nodeIndex) const { return (2 * nodeIndex) + 1; } // end getLeftChildIndex template int ArrayMaxHeap::getRightChildIndex(const int nodeIndex) const { return (2 * nodeIndex) + 2; } // end getRightChildIndex template int ArrayMaxHeap::getParentIndex(const int nodeIndex) const { return (nodeIndex - 1) / 2; } // end getParentIndex template bool ArrayMaxHeap::isLeaf(const int nodeIndex) const { return (getLeftChildIndex(nodeIndex) >= itemCount); } // end isLeaf template void ArrayMaxHeap::heapRebuild(const int subTreeNodeIndex) { // hints: percolation down, heapify if (!isLeaf(subTreeNodeIndex)) { // Find larger child int leftChildIndex = getLeftChildIndex(subTreeNodeIndex); int rightChildIndex = getRightChildIndex(subTreeNodeIndex); int largerChildIndex = rightChildIndex; // make assumption // Check to see if has rightChild and then check if left is larger if ( (largerChildIndex >= itemCount) || (items[leftChildIndex] > items[rightChildIndex])) { largerChildIndex = leftChildIndex; // Asssumption was wrong } // end if // Swap with larger child if node value is smaller if (items[largerChildIndex] > items[subTreeNodeIndex]) { swap(items[largerChildIndex], items[subTreeNodeIndex]); // Continue with the recursion at that child heapRebuild(largerChildIndex); } // end if } // end if } // end heapRebuild template void ArrayMaxHeap::heapCreate() { for (int index = itemCount / 2; index >= 0; index--) { heapRebuild(index); } // end for } // end heapCreate //****************************************************************** // // Public methods start here // //****************************************************************** template ArrayMaxHeap::ArrayMaxHeap(): itemCount(0), maxItems(DEFAULT_CAPACITY) { items = std::make_unique(DEFAULT_CAPACITY); } // end default constructor template ArrayMaxHeap:: ArrayMaxHeap(const ItemType someArray[], const int arraySize): itemCount(arraySize), maxItems(2 * arraySize) { // Allocate the array items = std::make_unique(2 * arraySize); // Copy given values into the array for (int i = 0; i  ArrayMaxHeap::~ArrayMaxHeap() { items.reset(); } // end destructor template bool ArrayMaxHeap::isEmpty() const { return itemCount == 0; } // end isEmpty template int ArrayMaxHeap::getHeight() const { return ceil(log2(itemCount + 1)); } // end getHeight template void ArrayMaxHeap::collectNodeInOrder(int i, vector& ans ) const { if ( i  int getLevel (int i ) { int j = i+1; int level = -1 ; while (j>0 ) { j /=2 ; level++; } return level ; } template void ArrayMaxHeap::printGraph() const { // xxx your codes // xxx hints: make use of function collectNodeInOrder } template int ArrayMaxHeap::getNumberOfNodes() const { return itemCount; } // end getNumberOfNodes template void ArrayMaxHeap::clear() { itemCount = 0; } // end clear template ItemType ArrayMaxHeap::peekTop() const { return items[0]; } // end peekTop template bool ArrayMaxHeap::add(const ItemType& newData) { bool isSuccessful = false; if (itemCount  0) && !inPlace) { int parentIndex = getParentIndex(newDataIndex); if (items[newDataIndex]  bool ArrayMaxHeap::remove() { bool isSuccessful = false; if (!isEmpty()) { items[ROOT_INDEX] = items[itemCount - 1]; itemCount--; heapRebuild(ROOT_INDEX); isSuccessful = true; } // end if return isSuccessful; } // end remove

This is the ArrayMeaxHeap.h file:

// Created by Frank M. Carrano and Tim Henry. // Copyright (c) 2016 __Pearson Education__. All rights reserved. /** Array-based implementation of the ADT heap. Listing 17-2. @file ArrayMaxHeap.h */ #ifndef ARRAY_MAX_HEAP_ #define ARRAY_MAX_HEAP_ #include "HeapInterface.h" #include "PrecondViolatedExcep.h" #include  #include  #include  using namespace std; template class ArrayMaxHeap : public HeapInterface { private: static const int ROOT_INDEX = 0; // Helps with readability static const int DEFAULT_CAPACITY = 21; // Small capacity to test for a full heap std::unique_ptr items; // Array of heap items int itemCount; // Current count of heap items int maxItems; // Maximum capacity of the heap // --------------------------------------------------------------------- // Most of the private utility methods use an array index as a parameter // and in calculations. This should be safe, even though the array is an // implementation detail, since the methods are private. // --------------------------------------------------------------------- // Returns the array index of the left child (if it exists). int getLeftChildIndex(const int nodeIndex) const; // Returns the array index of the right child (if it exists). int getRightChildIndex(int nodeIndex) const; // Returns the array index of the parent node. int getParentIndex(int nodeIndex) const; // Tests whether this node is a leaf. bool isLeaf(int nodeIndex) const; // Converts a semiheap to a heap. void heapRebuild(int subTreeRootIndex); // Creates a heap from an unordered array. void heapCreate(); public: ArrayMaxHeap(); ArrayMaxHeap(const ItemType someArray[], const int arraySize); virtual ~ArrayMaxHeap(); // HeapInterface Public Methods: bool isEmpty() const; int getNumberOfNodes() const; void collectNodeInOrder (int i, vector& inorder ) const ; void printGraph() const; int getHeight() const; ItemType peekTop() const; bool add(const ItemType& newData); bool remove(); void clear(); }; // end ArrayMaxHeap // #include "ArrayMaxHeap.cpp" #endif

This is the main.cpp file (Disregard files for PrecondViolatedExcep.cpp and .h):

#include "ArrayMaxHeap.h" #include "ArrayMaxHeap.cpp" #include  #include  using namespace std; void display(std::string& anItem) { std::cout  arr ) { ArrayMaxHeap<:string>* heap1Ptr = new ArrayMaxHeap<:string>(); for (string x: arr ) { heap1Ptr->add( x ); } heap1Ptr->printGraph (); int main() { vector  arr { "51", "10", "17", "20", "30", "40", "50", "60", "70", "80", }; testHeap ( arr ); vector arr2 {"50","33", "30", "70", "20", "60", "40", "10", "80", }; testHeap ( arr2 ); return 0; } // end main

Heap level-order traversal: 80705051601740103020 (same as the sequence in th e array) Heap in-order traversal: 10513070206080175040 level 2: +51++601740 level 3: 1030 Heap level-order traversal: 807060502030401033 (same as the sequence in the array) Heap in-order traversal: 105033702080306040 level 0:+++ level 3:1033