CODE
MaxHeap.h
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
//Each Student will have a unique id
struct Student
{
int id;
string firstName, lastName;
double gpa;
};
//class MaxHeap represents a max heap that contains Student
objects. The underline data structure
//is a one dimensional array of Student.
class MaxHeap
{
private:
struct Student* stuArr; //an array of Student
int capacity, size;
public:
MaxHeap(int capacity);
~MaxHeap();
Student* getStuArr();
int getSize();
int getCapacity();
int isFound(int stuId);
bool heapIncreaseID(int index, Student oneStudentwithNewID);
bool heapInsert(int id, string firstName, string lastName,
double gpa);
void heapify(int index);
Student getHeapMax();
void extractHeapMax();
int leftChild(int parentIndex);
int rightChild(int parentIndex);
int parent(int childIndex);
void printHeap();
};
//Constructor to dynamically allocate memory for a heap with the
specified capacity
MaxHeap::MaxHeap(int capacity)
{
//---
}
//Destructor
//Before termination, the destructor is called to free the
associated memory occupied by the heap.
//and prints the number of nodes deleted by it.
MaxHeap::~MaxHeap()
{
//----
//----
cout << "\nThe number of deleted Students is: " <<
studentNum << endl;
}
//Finish all the remaining functions according to the project's
description
//----
//----
//----
void MaxHeap::printHeap()
{
//----
//----
cout << left;
cout << setw(8) << stuArr.id
<< setw(12) << stuArr.firstName
<< setw(12) << stuArr.lastName
<< setw(8) << fixed << setprecision(2)
<< stuArr.gpa << endl;
}
Assignment.cpp
#include <iostream>
#include <string>
//include the header file here
//----
using namespace std;
void printMenu();
void heapSort(MaxHeap* oneMaxHeap);
int main()
{
char input1 = 'Z';
string firstName, lastName;
int id, newID;
int capacity, index = -1; //1D array capacity and index
double gpa;
bool success = false;
Student oneStudent;
//a variable used to represent a MaxHeap object
MaxHeap* heap1 = nullptr;
printMenu();
do {
cout << "\nWhat action would you like to perform?"
<< endl;
cin.get(input1);
input1 = toupper(input1);
cin.ignore(20, '\n'); //flush the buffer
// matches one of the cases
switch (input1)
{
case 'C': //create empty Heap with the initial capacity
cout << "\nPlease enter the heap capacity: ";
//----
//----
cin.ignore(20, '\n'); //flush the buffer for above capacity
entered
break;
//delete the heap, call the destructor explicitly. Re-initialize
heap1
//with default capacity 5
case 'D':
cout << "\nDelete the heap" << endl;
//----
//----
break;
case 'E': //Extract the root, remove it from the heap
//----
//----
break;
case 'F': //Find a Student
cout << "\nEnter the student ID you want to search: ";
cin >> id;
cin.ignore(20, '\n'); //flush the buffer
//----
//----
break;
case 'I': //Insert a Student
cout << "\nEnter the student first name: ";
cin >> firstName;
cout << "\nEnter the student last name: ";
cin >> lastName;
cout << "\nEnter the student id: ";
cin >> id;
cout << "\nEnter the student gpa: ";
cin >> gpa;
cin.ignore(20, '\n'); //flush the buffer
//----
//----
break;
case 'K': //increase the ID
cout << "\nEnter the old student id you want to increase:
";
cin >> id;
cout << "\nEnter the new id: ";
cin >> newID;
cin.ignore(20, '\n'); //flush the buffer
//----
//----
break;
case 'M': //get the maximum node info.
//----
//----
break;
case 'P': //Print heap contents
//----
//----
break;
case 'S': //HeapSort
cout << "\nHeap sort. Students will be sorted in
increasing order of their IDs" << endl;
//----
//----
break;
case 'Q': //Quit
delete heap1;
break;
case '?': //Display Menu
printMenu();
break;
default:
cout << "Unknown action\n";
break;
}
} while (input1 != 'Q');
return 0;
}
//************************************************************
//The function displays the menu
void printMenu()
{
cout << "Choice\t\tAction\n";
cout << "------\t\t------\n";
cout << "C\t\tCreate a heap\n";
cout << "D\t\tDelete the heap\n";
cout << "E\t\tExtract max node\n";
cout << "F\t\tFind a student by ID\n";
cout << "I\t\tInsert a student\n";
cout << "K\t\tIncrease the ID\n";
cout << "M\t\tGet the max node\n";
cout << "P\t\tPrint the heap\n";
cout << "S\t\tHeap Sort\n";
cout << "Q\t\tQuit\n";
cout << "?\t\tDisplay Help\n\n";
}
//***************************************************************************
//Given a max heap, this function sorts all elements in
increasing order of
//their IDs. Note: we explicitly separate the HeapSort algorithm
with
//its underline MaxHeap data structure. You can put the sorted
elements inside
//another array, then print them out.
void heapSort(MaxHeap* oneMaxHeap)
{
//----
//----
//print out format is given as below
cout << left << setw(8) <<
stuArr[index].id
<< setw(12) << stuArr[index].firstName
<< setw(12) << stuArr[index].lastName
<< setw(8) << fixed << setprecision(2)
<< stuArr[index].gpa << endl;
}
Assignment Description:
- Please Write The Code Only Where It Asks To Add The Code Maxheap H Include Iostream Include Iomanip Include Stri 1 (204.22 KiB) Viewed 34 times
- Please Write The Code Only Where It Asks To Add The Code Maxheap H Include Iostream Include Iomanip Include Stri 2 (82.42 KiB) Viewed 34 times
- Please Write The Code Only Where It Asks To Add The Code Maxheap H Include Iostream Include Iomanip Include Stri 3 (36.99 KiB) Viewed 34 times
Command Command's Description 'C' 'D' This command will ask user to enter the capacity of a heap, it then create and intialize an Max Heap object with the specific capacity. This command call the destructor explicitly to delete the existing/current heap and re-initialize and create one new Max Heap object with the initial capacity set to be the default 5. This command allows user to delete and create multiple heaps within a single test case. This command extracts the root (also the max node) from the heap. If the heap is empty or hasn't been initialized yet, it should show the following message on screen: Empty heap, can NOT extract max If the heap is non-empty, first it will print: 'E' Before extract heap max operation: followed by the contents of the heap before the extracting root operation. It should then call the extracting root operation, last it will print the message: After extract heap max operation: followed by the contents of the heap after the extracting root operation so that a user can verify that the root is indeed removed successfully. This command ask user to enter a Student's id, it then search the heap by using the id, if it find the relevant Student object inside the heap, it print the following message on screen: Student with id: ?? is found Otherwise it print: Student with id: ?? is NOT found ?? is the id user entered for searching. This command inserts a new Student object inside the heap. tasks the user to enter the Student's first and last name, id and gpa, it then insert the relevant Student inside the heap. If insertion is successful, it prints, for example: Student "John Smith" is added T' Otherwise, it prints, for example: Student "John Smith" is NOT added where "John Smith" can be any other Student's name we might insert inside the heap.
This command increases a Student object's id. The command will first prompt the following message and ask the user to enter the old id, Enter the old student id you want to increase: it then ask the user to enter the new id. In case the new id is less than or equals to the old id, the function should show the following message on screen: Increase ID error: new id is smaller than current id In case the Student object with the old id doesn't exist inside the heap, the command should print: The old ID you try to increase does not exist Or in case the new id the user entered already exist inside the heap, the command should print: 'K' The new ID you entered already exist, increase ID operation failed Otherwise first print the following message on screen: Before increase ID operation: Followed by calling printHeap() to print out the contents of the heap before the increasing id operation. It then print the following message on screen: Student with old id: ?? is increased to new id: ?? After increase id operation: Followed by calling printHeap() again to print out the contents of the heap after the increasing id operation so that you can verify the operation. This command allow us to get the the max node's info of the heap (also the root). It should print out the Student object, such as the following one: The maximum heap node is: ||25000 James Zhang 3.89 The format for the maximum node is: 'M cout << left; cout << setw(8) << maxStudent.id << setw(12) << maxStudent. firstName << setw(12) << maxStudent.lastName << setw(8) « fixed « setprecision (2) << maxStudent.gpa << endl; If the heap is empty, the command should print: Empty heap, can NOT get max node This command call the printHeap() function on the heap and prints out the heap contents. If the heap is empty, it should show the following message on screen: 'P' Empty heap, no elements
This command will call heapSort(MaxHeap* one Max Heap) function on the parameterized one MaxHeap (which is a MaxHeap object). Note: we put heapSort() function inside Assignment3.cpp file, not Max Heap.h file to explicitly separate the heap sort algorithm from Max Heap data structure, i.e. a Max Heap is forever a max heap. We will use the operations inside Max Heap to sort the given one MaxHeap in increasing order of their IDs and print the relevant Student object out. See the following for one output example: 2000 3.47 'S' Joe Dow 4000 Robert Smith 3.31 7000 Mary Smith 3.21 8000 Linda Smith 3.12 13000 Mary Johnson 3.72 17000 Richard Brown 3.23 19000 John Smith 3.56 This command deletes the heap object we created and terminate the driver program. This command prints out the menu. 'O '?'
Choice Action C Create a heap D Delete the heap E Extract max node F Find a student by ID I Insert a student K Increase the ID M Get the max node P Print the heap S Heap Sort O Quit ? Display Help What action would you like to perform? с Please enter the heap capacity: 5 What action would you like to perform? I Enter the student first name: John Enter the student last name: Smith Enter the student id: 5000 Enter the student gpa: 3.56 Student "John Smith" is added What action would you like to perform? i Enter the student first name: Mary Enter the student last name: Johnson Enter the student id: 13000 Enter the student gpa: 3.72 Student "Mary Johnson" is added What action would you like to perform?
I Enter the student first name: Joe Enter the student last name: Dow Enter the student id: 2000 Enter the student gpa: 3.47 Student "Joe Dow" is added What action would you like to perform? P Heap capacity = 5 Heap size = 3 13000 5000 2000 Mary John Joe Johnson Smith Dow 3.72 3.56 3.47 What action would you like to perform? I Enter the student first name: James Enter the student last name: Zhang Enter the student id: 2000 Enter the student gpa: 3.89 Duplicated Student. Not added Student "James Zhang" is NOT added What action would you like to perform? I Enter the student first name: James Enter the student last name: Zhang Enter the student id: 25000 Enter the student gpa: 3.89
What action would you like to perform? I Enter the student first name: Mary Enter the student last name: Smith Enter the student id: 7000 Enter the student gpa: 3.21 Student "Mary Smith" is added What action would you like to perform? P Heap capacity = 5 Heap size = 5 25000 13000 2000 5000 7000 James Mary Joe John Mary Zhang Johnson Dow Smith Smith 3.89 3.72 3.47 3.56 3.21 What action would you like to perform? I Enter the student first name: Richard Enter the student last name: Brown Enter the student id: 17000 Enter the student gpa: 3.23 Reach the capacity limit, double the capacity now. The new capacity now is 10 Student "Richard Brown" is added What action would you like to perform? P Heap capacity = 10 Heap size = 6 25000 13000 17000 5000 7000 2000 James Mary Richard John Mary Joe Zhang Johnson Brown Smith Smith Dow 3.89 3.72 3.23 3.56 3.21 3.47