Complete using the given code: Implement a MaxHeap and HeapSort. We are providin
ID: 3707390 • Letter: C
Question
Complete using the given code:
Implement a MaxHeap and HeapSort. We are providing some sample code and input files:
demo.cpp <- main method to try your implementation
inputs <- folder with several sample inputs
maxheap.cpp <- the actual implementation )only file you have to modify)
maxheap.hpp <- header file
The code provided follows closely the implementation in the textbook. •
To compile, run $ g++ -o heapsort demo.cpp maxheap.cpp • To test your implementation with a sample input file, run $ ./heapsort inputs/input.10.1 This will test a few methods (you need to check the maxheap after each step manually), and run heapsort (the code will check whether the output is sorted automatically). • To test your implementation with all sample files with one command, time for f in inputs/input.10*; do echo $f; ./heapsort $f; done The command time will let you know how long it took to run the code. You may want to store the output in a file so that you can look at it carefully: time for f in inputs/input.10*; do echo $f; ./heapsort $f; done > output
maxheap.hpp:
#include <vector>
using namespace std;
class MaxHeap {
private:
vector<int> arr;
int left(int parent);
int right(int parent);
int parent(int child);
void percolateDown(int index); // used for giving the heap max heap structure
void percolateUp(int index); // used for inserting in the heap at proper position
void heapify();
void buildHeap(vector<int> A,int n);
public:
MaxHeap();
~MaxHeap();
void insert(int element);
int deleteMax();
void display();
void heapsort(vector<int>& A,int n);
int size();
};
maxheap.cpp
#include "maxheap.hpp"
#include <stdio.h>
#include <iostream>
MaxHeap::MaxHeap() {}
MaxHeap::~MaxHeap() {}
/*
ALL YOUR CODE GOES HERE
The methods below either
- don't do anything at all, or
- return 0 just so that the code compiles
You have to implement every method in this class
*/
int MaxHeap::size() {
return 0;
}
int MaxHeap::left(int parent) {
return 0;
}
int MaxHeap::right(int parent) {
return 0;
}
int MaxHeap::parent(int child) {
return 0;
}
void MaxHeap::insert(int element) {
}
int MaxHeap::deleteMax() {
return 0;
}
void MaxHeap::display() {
vector<int>::iterator it;
cout << "MaxHeap:- ";
for(it=arr.begin(); it!=arr.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
void MaxHeap::percolateUp(int index) {
}
void MaxHeap::percolateDown(int index) {
}
void MaxHeap::buildHeap(vector<int> A,int n) {
}
void MaxHeap::heapsort(vector<int>& A,int n) {
}
demo.cpp
#include "maxheap.hpp"
#include <stdio.h>
#include <iostream>
int main(int argc, char*argv[]) {
//demo functions of the maxheap class
MaxHeap* myheap = new MaxHeap();
cout << "========================================" << endl;
cout << "Trying some methods from the MaxHeap class ...." << endl;
cout << "You must check that the output is correct manually (or write code that does it automatically)" << endl ;
cout << "========================================" << endl;
myheap->insert(700);
cout << "insert 700" << endl;
myheap->display();
myheap->insert(500);
cout << "insert 500" << endl;
myheap->display();
myheap->insert(100);
cout << "insert 100" << endl;
myheap->display();
myheap->insert(800);
cout << "insert 800" << endl;
myheap->display();
myheap->insert(200);
cout << "insert 200" << endl;
myheap->display();
myheap->insert(400);
cout << "insert 400" << endl;
myheap->display();
myheap->insert(900);
cout << "insert 900" << endl;
myheap->display();
int heapSize = myheap->size();
for ( int i = 0; i < heapSize/2; i++ ) {
cout << "Get and delete max element: " << myheap->deleteMax() << endl;
myheap->display();
}
cout << "========================================" << endl;
delete myheap;
//heapsorting numbers in a file
vector<int> A;
if(argc!=2) {
cout<<"Provide an input file as argument";
} else {
FILE *file = fopen(argv[1], "r");
if(file == 0){
cout << "ERROR: file does not exist" << endl;
return -1;
}
else {
int x;
fscanf(file, "%d", &x);
while(!feof(file)) {
A.push_back(x);
fscanf(file, "%d", &x);
}
fclose(file);
}
}
int n = A.size();
cout << endl << endl;
cout << "========================================" << endl;
cout << "Checking if HeapSort works ..." << endl;
cout << "Input size: " << n << endl;
cout << "========================================" << endl;
if (n <= 10) {
cout << "This it the input:" << endl;
for(int i=0; i<n; ++i) {
cout << A[i] << " ";
}
cout << endl;
}
else{
cout << "Input is too large to display" << endl;
}
MaxHeap *myheap2 = new MaxHeap();
myheap2->heapsort(A,n);
if (n <= 10) {
cout << "And this is the sorted output:" << endl;
for(int i=0; i<n; ++i) {
cout << A[i] << " ";
}
cout << endl;
}
else {
cout << "Sorted output is too large to display" << endl;
}
cout << "Checking if the output is actually sorted ..." << endl;
bool sorted = true;
for (int i=1; i<n; ++i) {
if (A[i-1] > A[i]){
cout << "Output is NOT SORTED: " << A[i-1] << " is greater than " <<
A[i] << "(index " << i << ")" << endl;
sorted = false;
}
}
if (sorted) {
cout << " The output is sorted" << endl;
}
cout << "========================================" << endl << endl << endl << endl;
delete myheap2;
return 0;
}
Explanation / Answer
#include<iostream>
#include<vector>
//#include<algorithm>
using namespace std;
class Maxheap
{
private:
vector<int>arr;
public:
int size()
{
return arr.size();
}
bool empty()
{
return (size()== 0);
}
int left(int parent)
{
return (2*parent + 1);
}
int right(int parent)
{
return (2*parent + 2);
}
int parent(int child)
{
return (child - 1 )/ 2;
}
void insert(int element)
{
arr.push_back(element); // add new element to the end of vector
int index = size() - 1;
percolateUp(index);
}
int deleteMax()
{
arr[0] = arr.back();
arr.pop_back();
percolateDown(0);
}
void display()
{
vector<int>::iterator it;
cout << "Maxheap:- ";
for (it = arr.begin(); it != arr.end(); ++it)
cout << *it << " ";
}
void percolateUp(int index)
{
if (index && arr[parent(index)] < arr[index])
{
swap(arr[index], arr[parent(index)]);
percolateUp(parent(index));
}
}
void percolateDown(int index)
{
int left_ind = left(index);
int right_ind = right(index);
int largest = index;
if (left_ind < size() && arr[left_ind] > arr[index])
largest = left_ind;
if (right_ind < size() && arr[right_ind] > arr[largest])
largest = right_ind;
if (largest != index)
{
swap(arr[index], arr[largest]);
percolateDown(largest);
}
}
void Heapify(int i)
{
int left_ind = left(i);
int right_ind = right(i);
int smallest = i;
if (left_ind < size() && arr[left_ind] < arr[i])
smallest = left_ind;
if (right_ind < size() && arr[right_ind] < arr[smallest])
smallest = right_ind;
if (smallest != i)
{
swap(arr[i], arr[smallest]);
Heapify(smallest);
}
}
void buildHeap(vector<int> A, int n)
{
vector<int>::iterator it;
for (it = A.begin(); it != A.end(); it++)
arr.push_back(*it);
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.