The code needs to go in heap.cpp the other files are just for reference

//main.cpp

#include #include #include #include "MaxHeap.h" #include "MinHeap.h"

using namespace std;

// Use this main() function to test your code. You may change things as you // wish here, this is for your own use. Please note: This code will not be used // for grading.

int main() { // Creating a heap vector elems = {4, 10, 30, 90, 110, 150, 300, 500}; MinHeap myHeap(elems);

// Printing a heap cout

// Testing your answer vector leafNodes = lastLevel(myHeap); cout

// Checking correctness vector expected = {500}; if (expected == leafNodes) cout

return 0; }

//heap.cpp

#include using namespace std; #include "MinHeap.h"

vector lastLevel(MinHeap heap) { // Your code here }

//MaxHeap.cpp

#include "MaxHeap.h"

MaxHeap::MaxHeap(const vector & vector) { int inf = numeric_limits::max(); elements.push_back(inf); elements.insert(elements.end(), vector.begin(), vector.end()); buildHeap(); }

MaxHeap::MaxHeap() { int inf = numeric_limits::max(); elements.push_back(inf); }

void MaxHeap::buildHeap() { std::sort(elements.begin() + 1, elements.end(), std::greater()); }

void MaxHeap::heapifyDown(int index) { int length = elements.size(); int leftChildIndex = 2 * index; int rightChildIndex = 2 * index + 1;

if (leftChildIndex >= length) return; // index is a leaf

int maxIndex = index;

if (elements[index]

if ((rightChildIndex

if (maxIndex != index) { // need to swap int temp = elements[index]; elements[index] = elements[maxIndex]; elements[maxIndex] = temp; heapifyDown(maxIndex); } }

void MaxHeap::heapifyUp(int index) { if (index

int parentIndex = index / 2;

if (elements[parentIndex]

void MaxHeap::insert(int newValue) { int length = elements.size(); elements.push_back(newValue); heapifyUp(length); }

int MaxHeap::peek() const { return elements.at(1); }

int MaxHeap::pop() { int length = elements.size(); int p = -1;

if (length > 1) { p = elements[1]; elements[1] = elements[length - 1]; elements.pop_back(); heapifyDown(1); }

return p; }

void MaxHeap::print() const { if (elements.size() > 1) { int length = elements.size(); cout

//Maxheap.h

#ifndef MAXHEAP_H #define MAXHEAP_H #include #include "vector" #include #include using namespace std;

class MaxHeap { public: /** * @elements: stores the integers in the heap. */ vector elements;

/** * @heapifyDown: performs heapifyDown algorithm starting from index all the * way down the heap. */ void heapifyDown(int index);

/** * @heapifyUp: performs heapifyUp algorithm starting from index all the way * up the heap. */ void heapifyUp(int index);

/** * @buildHeap: this is the buildHeap algorithm. It is called when a new heap * object is created. */ void buildHeap();

/** * Constructor: constructs a MaxHeap from the given integer vector. */ MaxHeap(const vector & vector);

/** * Empty constructor: constructs an empty MaxHeap. */ MaxHeap();

/** * @insert: inserts an integer into the MinHeap. */ void insert(int newValue);

/** * @peek: returns the value of the element at the top of the heap. Does not * modify the heap. */ int peek() const;

/** * @pop: returns the value of the element at the top of the heap and removes * it from the heap. */ int pop();

/** * @print: prints out the array of elements in the heap. */ void print() const; };

#endif // MAXHEAP_H

//MinHeap.cpp

#include "MinHeap.h"

MinHeap::MinHeap(const vector & vector) { int inf = numeric_limits::min(); elements.push_back(inf); elements.insert(elements.end(), vector.begin(), vector.end()); buildHeap(); }

MinHeap::MinHeap() { int inf = numeric_limits::min(); elements.push_back(inf); }

void MinHeap::buildHeap() { std::sort(elements.begin() + 1, elements.end()); }

void MinHeap::heapifyDown(int index) { int length = elements.size(); int leftChildIndex = 2 * index; int rightChildIndex = 2 * index + 1;

if (leftChildIndex >= length) return; // index is a leaf

int minIndex = index;

if (elements[index] > elements[leftChildIndex]) { minIndex = leftChildIndex; }

if ((rightChildIndex elements[rightChildIndex])) { minIndex = rightChildIndex; }

if (minIndex != index) { // need to swap int temp = elements[index]; elements[index] = elements[minIndex]; elements[minIndex] = temp; heapifyDown(minIndex); } }

void MinHeap::heapifyUp(int index) { if (index

int parentIndex = index / 2;

if (elements[parentIndex] > elements[index]) { int temp = elements[parentIndex]; elements[parentIndex] = elements[index]; elements[index] = temp; heapifyUp(parentIndex); } }

void MinHeap::insert(int newValue) { int length = elements.size(); elements.push_back(newValue); heapifyUp(length); }

int MinHeap::peek() const { return elements.at(1); }

int MinHeap::pop() { int length = elements.size(); int p = -1;

if (length > 1) { p = elements[1]; elements[1] = elements[length - 1]; elements.pop_back(); heapifyDown(1); }

return p; }

void MinHeap::print() const { if (elements.size() > 1) { int length = elements.size(); cout

//MinHeap.h

#ifndef MINHEAP_H #define MINHEAP_H

#include #include #include #include using namespace std;

class MinHeap { public: /** * @elements: stores the integers in the heap. */ vector elements;

/** * @heapifyDown: performs heapifyDown algorithm starting from index all the * way down the heap. */ void heapifyDown(int index);

/** * @heapifyUp: performs heapifyUp algorithm starting from index all the way * up the heap. */ void heapifyUp(int index);

/** * @buildHeap: this is the buildHeap algorithm. It is called when a new heap * object is created. */ void buildHeap();

/** * Constructor: constructs a MinHeap from the given integer vector. */ MinHeap(const vector & vector);

/** * Empty constructor: constructs an empty MinHeap. */ MinHeap();

/** * @insert: inserts an integer into the MinHeap. */ void insert(int newValue);

/** * @peek: returns the value of the element at the top of the heap. Does not * modify the heap. */ int peek() const;

/** * @pop: returns the value of the element at the top of the heap and removes * it from the heap. */ int pop();

/** * @print: prints out the array of elements in the heap. */ void print() const; };

#endif // MINHEAP_H

The Problem Implement the following function in heap.cpp vector int> last Level (MinHeap heap); Given a MinHeap (see MinHeap.h), return a vector containing the leaf nodes at the last leve Example 1 input Heap: [-inf,1,3,5,7,9,11] Output: 17,9, 11] Visual aid: 7 9 11 Example 2: Input Heap: -inf, 1,3, 7,9] Output: 17,91 Visual aid: 3 5 7 9 Hint: you can calculate $Nog2m)inCV as follows. (Therearesomesolutionsthatdonotusethelog2$ function.) int m, logm; logm sted log2 (m)