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

Question

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

//main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
#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<int> elems = {4, 10, 30, 90, 110, 150, 300, 500};
MinHeap myHeap(elems);

// Printing a heap
cout << "myHeap: " << endl;
myHeap.print();

// Testing your answer
vector<int> leafNodes = lastLevel(myHeap);
cout << "The leaf nodes are" << endl;
for (size_t i = 0; i < leafNodes.size(); i ++)
cout << leafNodes[i] << ' ';
cout << endl;

// Checking correctness
vector<int> expected = {500};
if (expected == leafNodes)
cout << "Your output is correct" << endl;
else
cout << "Your output is incorrect" << endl;

return 0;
}

//heap.cpp

#include <cmath>
using namespace std;
#include "MinHeap.h"

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

//MaxHeap.cpp

#include "MaxHeap.h"

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

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

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

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] < elements[leftChildIndex]) {
maxIndex = leftChildIndex;
}

if ((rightChildIndex < length)
&& (elements[maxIndex] < elements[rightChildIndex])) {
maxIndex = 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 < 2)
return;

int parentIndex = index / 2;

if (elements[parentIndex] < elements[index]) {
int temp = elements[parentIndex];
elements[parentIndex] = elements[index];
elements[index] = temp;
heapifyUp(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 << "[";
for (int i = 1; i < length - 1; i++) {
cout << elements[i] << ", ";
}
cout << elements[elements.size() - 1] << "]" << endl;
} else {
cout << "[ ]" << endl;
}
}

//Maxheap.h

#ifndef MAXHEAP_H
#define MAXHEAP_H
#include <iostream>
#include "vector"
#include <algorithm>
#include <limits>
using namespace std;

class MaxHeap
{
public:
/**
* @elements: stores the integers in the heap.
*/
vector<int> 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<int> & 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<int> & vector)
{
int inf = numeric_limits<int>::min();
elements.push_back(inf);
elements.insert(elements.end(), vector.begin(), vector.end());
buildHeap();
}

MinHeap::MinHeap()
{
int inf = numeric_limits<int>::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 < length)
&& (elements[minIndex] > 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 < 2)
return;

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 << "[";
for (int i = 1; i < length - 1; i++) {
cout << elements[i] << ", ";
}
cout << elements[elements.size() - 1] << "]" << endl;
} else {
cout << "[ ]" << endl;
}
}

//MinHeap.h

#ifndef MINHEAP_H
#define MINHEAP_H

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class MinHeap
{
public:
/**
* @elements: stores the integers in the heap.
*/
vector<int> 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<int> & 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)

Explanation / Answer

The approach is, find the righmost internal node.Once we find the rightmost internal node, all elements following it will be leafs at last level;

Include the declaration of vector<int> lastLevel(MinHeap heap) in MinHeap.h

Below is the code for lastlevel

heap.cpp

#include <cmath>
using namespace std;
#include "MinHeap.h"

vector<int> lastLevel(MinHeap heap)
{
     int len=heap.elements.size();

     int rightmostIndex=1;
     while(1)
     {
       if((2*rightmostIndex+1)>=len)
        break;
       rightmostIndex=2*rightmostIndex+1;
     }
   
     if(rightmostIndex+1==len)
       rightmostIndex/=2;
   
     vector<int> leaf;
     for(int i=rightmostIndex+1;i<len;i++)
        leaf.push_back(heap.elements[i]);
     return leaf;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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