In this assignment, you are given several classes in the cpp file “Heap.cpp” . Y
ID: 3706012 • Letter: I
Question
In this assignment, you are given several classes in the cpp file “Heap.cpp”. Your task is to complete the implementation of the classes specified as below.
1. Your Task
You are given a class “TNode” that contains one integer value, and three pointers – one to the parent, one to the left child, and one to the right child. You need to complete the class “minHeap” and other functions specified in the cpp file.
Task 1: Implement the constructors (default and copy) of Heap. You need to make sure that the copy constructor makes a separate copy of the heap.
Task 2: Implement in, removemin, getmin. Note:
• getmin returns the pointer to the min element, but do not modify the heap. On the other hand, removemin just deletes the min element from the heap.
• In this homework, I request that the in function takes input “const TNode t”, which means you cannot modify the input node t. You should create a new node (different from the input node t) and then add into the heap.
• It is highly recommended to write helper functions, such as bubble-up and bubble-down. If you don’t know what they are, you should review heap.
Task 3: Implement Heapify that takes input a binary tree, and makes a heap from the binary tree. Here your binary tree is in the array form. You cannot modify the array.
Task 4: Implement Heapsort that takes input an array of size n, and returns a sorted array.
Task 5: Design a test function of your own design. Test everything!
“Heap.cpp” file
#include
using namespace std;
class TNode
{
public:
int val;
TNode(){}
TNode(int v){val = v;}
TNode * left;
TNode * right;
TNode * parent;
};
class minHeap // binary heap
{
int size;
TNode *top;
public:
minHeap();
minHeap(const minHeap &h);
void in(const TNode &t);// you should new a new node and then add into
the heap
void removemin();
Node* getmin();
void Heapify(const int n, const int *p);// p is an array of size n,
representing a (full) binray tree of size n-1. (The tree starts at
location 1). You should not modify the array p.
};
int * HeapSort(const int n, const int *arr);// arr is an integer array of
numbers.
//You should output a pointer
to a new array which is a sorted version of arr
void Test() // write a test for your implementation
{
}
int main(int argc, const char * argv[]) {
return 0;
}
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BinaryHeap
{
private:
vector <int> heap;
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BinaryHeap()
{}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void DisplayHeap();
int Size();
};
int BinaryHeap::Size()
{
return heap.size();
}
void BinaryHeap::Insert(int element)
{
heap.push_back(element);
heapifyup(heap.size() -1);
}
void BinaryHeap::DeleteMin()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}
void BinaryHeap::DisplayHeap()
{
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end())
{
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
int BinaryHeap::left(int parent)
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
int BinaryHeap::right(int parent)
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
int BinaryHeap::parent(int child)
{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
void BinaryHeap::heapifyup(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
int temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}
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)
{
int temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}
int main()
{
BinaryHeap h;
while (1)
{
cout<<"------------------"<<endl;
cout<<"Operations on Heap"<<endl;
cout<<"------------------"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Print Heap"<<endl;
cout<<"5.Exit"<<endl;
int choice, element;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>element;
h.Insert(element);
break;
case 2:
h.DeleteMin();
break;
case 3:
cout<<"Minimum Element: ";
if (h.ExtractMin() == -1)
{
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.DisplayHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}