Write a program that implements a class for a binary minHeap data structure. Imp

Question

Write a program that implements a class for a binary minHeap data structure.

Implement your heap using an array. The minHeap must implement the following functions:

void insert(Event); // the minHeap insert algorithm

void add(Event); // adds the event to the next available array slot, no percolation

Event deleteMin(); // removes and returns the event with the smallest timeOfEvent

boolean isEmpty();

void buildHeap(); // the minHeap buildHeap algorithm

“Event” is a base class for three types of events, Arrival, EndOfService and Termination. Each of these has a class variable, double timeOfEvent, and a function void print() that is called when the object is removed from the queue. These print functions print the class name followed by the class variable, as follows:

Arrival Event at time 24.56.

EndOfService Event at time 50.66.

Termination Event at time 71.78.

All doubles must be printed with two digits before the point and two digits after the point. The timeOfEvent field is used as the key for all heap operations.

An input must be read from System.in and all output must be to System.out.

Sample Run:

1. Add Event

2. Insert

3. Print Array

4. Build Heap

5. Delete Min

6. Quit

Option: 1

Event Type: Arrival

Time: 12.10

Done

Option: 1

Event Type: Arrival

Time: 11.45

Done

Option: 1

Event Type: EndOfService

Time: 11.40

Done

Option: 1

Event Type: Termination

Time: 13.45

Done

Option: 2

Can’t insert into the heap use build heap first or just add

Option: 3 Arrival:12.10; Arrival:11.45; EndOfService:11.40; Termination: 13.45

Option: 4 Heap Built

Option: 3 EndOfService :11.40; Arrival:11.45; Arrival:12.10; Termination:13.45

Option: 2 Event Type: Arrival Time: 13.40

Option: 1 Can’t add into the heap use insert

Option: 7 Minimum Deleted EndOfService Event at time 11.40

Option: 3 Arrival:11.45; Arrival 13:40; Arrival:12.10; Termination:13.45

Option: 8 Thank You.

Explanation / Answer

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;

class BinaryHeap
{
private:
vector <string> heap;
vector <float> time;

public:
BinaryHeap()
{}
void BinaryHeap::buildHeap()
{
  
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void DisplayHeap();
int Size();
};

void BinaryHeap::AddEvent(String event, float time1)
{
vector <string>::iterator pos = heap.begin();
vector <float>::iterator pos1 = time.begin();
while (pos != heap.end() && pos1 != time.end())
{
heap.push_back(event);
time.push_back(time1);
pos++;
pos1++;
}

}
int BinaryHeap::Size()
{
return heap.size(),time.size();
  
}

/*
* Insert Element into a Heap
*/
void BinaryHeap::Insert(string element, float time1)
{
try{
heap.push_back(element);
time.push_back(time1);
heapifyup(heap.size() -1);
heapifyup(time.size() -1);
} catch(...)
{
cout<<"Can’t insert into the heap use build heap first or just add";
}
}
/*
* Delete Minimum Element
*/
void BinaryHeap::DeleteMin()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
time[0] = time.at(time.size() - 1);
heap.pop_back();
time.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}

/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector <string>::iterator pos = heap.begin();
vector <float>::iterator pos1 = time.begin();
while (pos != heap.end() && pos1 != time.end())
{
cout<<*pos<<":"<<*pos1;
pos++;
pos1++;
}
cout<<endl;
}

/*
* Return Left Child
*/
int BinaryHeap::left(int parent)
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}

/*
* Return Right Child
*/
int BinaryHeap::right(int parent)
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}

/*
* Return Parent
*/
int BinaryHeap::parent(int child)
{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}

/*
* Heapify- Maintain Heap Structure bottom up
*/
void BinaryHeap::heapifyup(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
string temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}

/*
* Heapify- Maintain Heap Structure top down
*/
void BinaryHeap::heapifydown(int in)
{

int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0)
{
string temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}

/*
* Main Contains Menu
*/
int main()
{
BinaryHeap h;
while (1)
{
cout<<"------------------"<<endl;
cout<<"Operations on Heap"<<endl;
cout<<"------------------"<<endl;
cout<<"1.Add Event"<<endl;
cout<<"2.Insert Element"<<endl;
cout<<"3.Print Array"<<endl;
cout<<"4.Build Heap"<<endl;
cout<<"5.Delete Minimum Element"<<endl;
cout<<"6.Exit"<<endl;
int choice;
string element;
float time;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Event Type: ";
cin>>element;
cout<<"Time: ";
cin>>time;
h.AddEvent(element,time);
break;
case 2:
cout<<"Event Type: ";
cin>>element;
cout<<"Time: ";
cin>>time;
h.Insert(element,time);
break;
case 3:
h.DisplayHeap();
case 4:
h.buildHeap();
case 5:
h.DeleteMin()
case 6:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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