Everything has to be done in C++ You need to define the following data types. EL
ID: 3805962 • Letter: E
Question
Everything has to be done in C++
You need to define the following data types. ELEMENT is a data type that contains a field named key, which is of type int. In later assignments, you will have to add on other fields to ELEMENT without having to change the functions. Note that ELEMENT should not be of type int HEAP is a data type that contains three fields named capacity (of type int), size (of type int) and H (an array of type ELEMENT with index ranging from 0 to capacity The functions that you are required to implement are Initialize(n) which returns an object of type HEAP with capacity n and size 0. BuildHeap(heap, A), where heap is a HEAP object and A i an array of type ELEMENT This s function copies the elements in A into heap->H and uses the linear time build heap algorithm to obtain a heap of size size(A). Insert (heap, k) which inserts an element with key equal to k into the min-heap heap. Delete Min(heap) which deletes the element with minimum key and returns it to the caller Decrease Key(heap, element, value) which decreases the key field of element to value, if the latter is not larger than the former. Note that you have make necessary adjustment to make sure that heap order is maintained. print Heap(heap) which prints out the heap information, including capacity, size and the key fields of the elements in the array with index going from 1 to sizeExplanation / Answer
util.h
#ifndef UTIL_H
#define UTIL_H
int nextCommand(int& , int&);
void errorOut(int);
void warningOut(int);
#endif /*UTIL_H */
main.cpp
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <stdio.h>
#include "heap.h"
#include "debug.h"
#include "util.h"
#include "fileio.h"
bool display_command = false;
using namespace std;
Element *a;
void MakeElementArray(int size)
{
a = new Element[size];
}
int main(int argc, char** argv) {
int i, v;
HEAP heap;
bool heap_created = false;
char command;
char exit_command = 's';
while( command != exit_command)
{
if(display_command){cout << "Waiting for next command ";}
command = nextCommand(i, v);
switch (command)
{
case 'k':
case 'K':
if(display_command){printf("COMMAND: %c %d %d ", command, i, v);}
if(heap_created)
{
if(i > heap.get_size())
{
errorOut(8);
}
//CHECK IF VALUE IS LARGER THAN EXISTING VALUE
if(v > heap.get_element(i).key)
IncreaseKeyHeap(heap, i, v);
else
errorOut(4);
}
else
errorOut(1);
break;
case 'r':
case 'R':
if(display_command){printf("COMMAND: %c ", command);}
if(heap_created)
{
int size;
size = ReadInputFile();
if(size == 0)
break;
MakeElementArray(size);
ReadInputFile(heap, a, size);
BuildHeap(heap, a, size);
}
else
errorOut(1);
break;
case 'w':
case 'W':
if(display_command){printf("COMMAND: %c ", command);}
if(heap_created)
PrintHeap(heap);
else
errorOut(1);
break;
case 'i':
case 'I':
if(display_command){printf("COMMAND %c %d ", command, i);}
if(heap_created)
{
if(heap.get_size() < heap.get_capacity())
InsertHeap(heap, i);
else
errorOut(3);
}
else
errorOut(1);
break;
case 'd':
case 'D':
if(display_command){printf("COMMAND: %c ", command);}
if(heap_created)
{
if(heap.get_size() <= 0)
{
errorOut(9);
break;
}
else
cout << DeleteMaxHeap(heap) << " ";
}
else
errorOut(1);
break;
case 'c':
case 'C':
if(display_command){printf("COMMAND: %c %d ", command, i);}
if(!heap_created)
{
if(i > 0)
{
heap = InitializeHeap(i);
heap_created = true;
}
else
errorOut(5);
}
else
errorOut(2);
break;
case 's':
case 'S':
if(display_command)
{
cout << "COMMAND: " << command << " ";
cout << " Exiting.. Goodbye! ";
}
command = 's';
break;
default: break;
}
}
return 0;
}
debug.cpp
#include <cstdlib>
#include <iostream>
using namespace std;
//Change this to 1 to display debug messages
int DEBUG=0;
void debug(string out)
{
if(DEBUG == 1)
{
cout << "DEBUG: ";
cout << out << " ";
}
}
void debug(int out)
{
if(DEBUG == 1)
{
cout << "DEBUG: ";
cout << out << " ";
}
}
void debug(string desc, int out)
{
if(DEBUG == 1)
{
cout << "DEBUG: " << desc << " ";
cout << out << " ";
}
}
debug.h
//Includes
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef DEBUG_H
#define DEBUG_H
//Function Prototypes
void debug(string);
void debug(int);
void debug(string, int);
#endif /* DEBUG_H */
fileio.cpp
#include "heap.h"
#include "util.h"
#include "fileio.h"
#include <fstream>
#include <iostream>
using namespace std;
string filename = "HEAPinput.txt";
//Reads just the first number in the file
int ReadInputFile()
{
int size;
string line;
ifstream inputfile(filename.c_str());
if(inputfile.is_open())
{
inputfile >> line;
size = atoi(line.c_str());
if(!size || size < 1)
{
errorOut(7);
return 0;
}
}
else
{
errorOut(6);
exit(0);
}
inputfile.close();
return size;
}
//reads from the second number to the last
void ReadInputFile(HEAP &i_heap, Element a[], int size)
{
int read_number;
int count = 0;
string line;
ifstream inputfile(filename.c_str());
if(inputfile.is_open())
{
inputfile >> line;
while(inputfile >> line)
{
read_number = atoi(line.c_str());
if(!read_number)
{
warningOut(2);
}
count ++;
if(count <= size && count + i_heap.get_size() <= i_heap.get_capacity() )
{
Element temp;
temp.key = read_number;
a[count-1] = temp;
}
if(i_heap.get_capacity() < count + i_heap.get_size())
warningOut(3);
}
if(count > size)
warningOut(1);
}
else
{
errorOut(6);
exit(0);
}
inputfile.close();
}
fileio.h
#ifndef FILEIO_H
#define FILEIO_H
#include "heap.h"
int ReadInputFile();
void ReadInputFile(HEAP&, Element[], int);
#endif /*FILEIO_H */
heap.h
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#ifndef HEAP_H
#define HEAP_H
struct Element
{
int key;
};
class HEAP {
public:
HEAP ();
HEAP (int, int, Element[]);
HEAP (int, int, int);
HEAP (int, int);
~HEAP(void);
void InsertHeap(HEAP, int);
void set_size_final(int fsize) {size_final=fsize;}
int get_size() {return size;}
void set_size(int n) {size=n;}
void inc_size() {size++;}
void dec_size() {size--;}
int get_capacity() {return capacity;}
Element get_element(int n) {return element[(n-1)];}
void set_element_key(int node, int key) {this->element[(node-1)].key = key;}
void set_element(int node, Element i_element) {this->element[(node-1)] = i_element;}
int get_parent(int node)
{
if(node == 1)
return NULL;
else
return floor(node/2);
}
Element get_parent_element(int node)
{
return (this->get_element(this->get_parent(node)));
}
bool parent_has_two_children(int node)
{
if(this->size >= this->get_parent(node)*2+1)
return true;
else
return false;
}
Element get_right_child_element(int node)
{
return this->get_element((2*node)+1);
}
int get_right_child(int node)
{
if(2*node+1 <= this->size)
return node*2+1;
else
return INT_MAX;
}
Element get_left_child_element(int node)
{
return this->get_element(2*node);
}
int get_left_child(int node)
{
if(node*2 <= this->get_size())
return node*2;
else
return INT_MAX;
}
bool is_element(int node)
{
if(node <= this->size)
return true;
else
return false;
}
void swap_with_parent(int node)
{
Element parent_element = this->get_parent_element(node);
this->set_element(this->get_parent(node), this->get_element(node));
this->set_element(node, parent_element);
return;
}
//Swap with right and return node of where orginal element is
int swap_with_right_child(int node)
{
Element current_element = this->get_element(node);
this->set_element(node, this->get_right_child_element(node));
this->set_element(this->get_right_child(node), current_element);
return this->get_right_child(node);
}
//Swap with left and return node of where orginal element is
int swap_with_left_child(int node)
{
Element current_element = this->get_element(node);
this->set_element(node, this->get_left_child_element(node));
this->set_element(this->get_left_child(node), current_element);
return this->get_left_child(node);
}
private:
int capacity;
int size;
int size_final;
Element *element;
};
HEAP InitializeHeap(int);
int DeleteMaxHeap(HEAP&);
void InsertToHeap(HEAP&, Element);
void InsertHeap(HEAP&, int);
void BuildHeap(HEAP&, Element[], int);
void IncreaseKeyHeap(HEAP&, int, int);
void PrintHeap(HEAP);
void Heapify(HEAP&, int);
void Sort_Heap(HEAP&);
#endif /* HEAP_H */
heap.cpp
#include <iostream>
#include <cstdlib>
#include <stdio.h>
using namespace std;
#include "heap.h"
#include "debug.h"
HEAP::HEAP(int h_capacity, int h_size, Element h_element[])
{
capacity = h_capacity;
size = h_size;
element = new Element[h_capacity];
for(int i = 0 ; i < h_size ; i ++ )
{
element[i] = h_element[i];
}
}
HEAP::HEAP()
{
}
HEAP::HEAP(int h_capacity, int h_size)
{
capacity = h_capacity;
element = new Element[h_capacity];
size = h_size;
}
HEAP::~HEAP(void)
{
element = new Element[1];
delete[] element;
}
HEAP InitializeHeap(int h_capacity)
{
HEAP return_heap(h_capacity, 0);
return return_heap;
}
void BuildHeap(HEAP &i_heap, Element a[], int size)
{
int init_size = i_heap.get_size();
debug("size of a", size);
debug("Size before build heap", i_heap.get_size());
//Make the heap in the order of the array
for (int i = init_size ; i < size+init_size && i < i_heap.get_capacity(); i++)
{
if(i > i_heap.get_capacity())
cout << "BIG ERROR";
InsertToHeap(i_heap, a[i-init_size]);
}
debug("Size after build heap", i_heap.get_size());
debug(i_heap.get_element(0).key);
debug("i",floor(i_heap.get_size()/2));
for(int i=floor(i_heap.get_size()/2); i >= 1 ; i--)
{
Heapify(i_heap, i);
}
}
void InsertToHeap(HEAP &i_heap, Element i_element)
{
//Inset to last element of the Heap
i_heap.inc_size();
i_heap.set_element(i_heap.get_size(), i_element);
//DEBUG STATMENT
//PrintHeap(i_heap);
}
void Heapify(HEAP &i_heap, int element)
{
debug("Heapify");
//PrintHeap(i_heap);
//Get the key values for the left and right elements
int left_key, right_key, largest;
int current_key = i_heap.get_element(element).key;
int left_node = i_heap.get_left_child(element);
int right_node = i_heap.get_right_child(element);
if(left_node <= i_heap.get_size())
{
left_key = i_heap.get_left_child_element(element).key;
if(left_key > current_key)
largest = left_node;
else
largest = element;
}
else
largest = element;
if(right_node <= i_heap.get_size())
{
right_key = i_heap.get_right_child_element(element).key;
if(right_key > i_heap.get_element(largest).key)
largest = right_node;
}
if(largest != element)
{
Element largest_element = i_heap.get_element(largest);
i_heap.set_element(largest, i_heap.get_element(element));
i_heap.set_element(element, largest_element);
Heapify(i_heap, largest);
}
}
void InsertHeap(HEAP &i_heap, int key)
{
//Make the new element
Element new_element;
new_element.key = key;
//Insert the new element into the Heap
InsertToHeap(i_heap, new_element);
for(int i=floor(i_heap.get_size()/2); i >= 1 ; i--)
{
Heapify(i_heap, i);
}
}
int DeleteMaxHeap(HEAP &i_heap)
{
Element deleted_element = i_heap.get_element(1);
i_heap.set_element(1, i_heap.get_element(i_heap.get_size()));
i_heap.dec_size();
for(int i=floor(i_heap.get_size()/2); i >= 1 ; i--)
{
Heapify(i_heap, i);
}
return deleted_element.key;
}
void IncreaseKeyHeap(HEAP &i_heap, int element, int key)
{
//Set the element key
i_heap.set_element_key(element, key);
while(element > 1 && i_heap.get_parent_element(element).key < key)
{
i_heap.swap_with_parent(element);
element = i_heap.get_parent(element);
}
}
void PrintHeap(HEAP i_heap)
{
cout << i_heap.get_capacity() << " ";
cout << i_heap.get_size() << " ";
for (int i=1 ; i <= i_heap.get_size() ; i++)
{
cout << i_heap.get_element(i).key << " ";
}
}
util.cpp
#include "util.h"
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
//=============================================================================
int nextCommand(int& i, int& v)
{
char c;
while(1)
{
scanf("%c", &c);
if(c == ' ' || c == ' ' || c == ' ')
{
continue;
}
if(c == 'S' || c == 'R' || c == 'W' || c == 'D' )
{
break;
}
if(c == 's' || c == 'r' || c == 'w' || c == 'd' )
{
break;
}
if(c == 'K' || c == 'k')
{
scanf("%d", &i);
scanf("%d", &v);
break;
}
if (c == 'C' || c == 'c')
{
scanf("%d", &i);
break;
}
if(c == 'I' || c == 'i')
{
scanf("%d", &i);
break;
}
printf("Invalid Command ");
}
return c;
}
void errorOut(int error_code)
{
cout << "ERROR: ";
switch(error_code)
{
case 1:
cout << "HEAP HAS NOT BEEN CREATED ";
break;
case 2:
cout << "HEAP HAS ALREADY BEEN CREATED ";
break;
case 3:
cout << "THE HEAP HAS HIT IS COMPACITY ";
break;
case 4:
cout << "PLEASE ENTER A VALUE THAT IS LARGER THAN THE EXISTING VALUE ";
break;
case 5:
cout << "COMPACITY MUST BE LARGER THAN 0 ";
break;
case 6:
cout << "CANT OPEN INPUT FILE ";
break;
case 7:
cout << "SIZE MUST BE LARGER THAN 0 ";
break;
case 8:
cout << "REQUESTED ELEMENT IS OUTSIDE OF THE SIZE OF THE HEAP ";
break;
case 9:
cout << "HEAP SIZE IS ALREADY AT 0, CAN NOT DELETE ANY MORE ";
break;
default:
cout << "UNKNOWN ERROR... QUITING";
exit(0);
break;
}
}
void warningOut(int warning_code)
{
cout << "WARNING: ";
switch(warning_code)
{
case 1:
cout << "MORE LINES IN THE THE INPUT FILE THAN LISTED AT THE TOP - ONLY READING THE NUMBER OF LINES LISTED AT THE TOP ";
break;
case 2:
cout << "NUMBER FROM FILE DOSENT APPARE TO BE A NUMBER (OR IS 0) ";
break;
case 3:
cout << "REQUESTED TO READ MORE LINES THE THE CAPACITY IS SET TO - WILL ONLY READ UPTO THE CAPACITY ";
break;
default:
cout << "UNKNOWN WARRNING... CONTINUING PROGRAM ";
break;
}
}
HEAPinput.txt
6
2
4
7
6
8
1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.