Homework SourseYou are given a class TNode that contains one integer value
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 “BTree” and two 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 Node 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 I am talking about, 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. 1
Task 5: Design a test function
Solution
/*
* C++ Program to Implement Binary Heap
*/
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
/*
* Class Declaration
*/
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();
};
/*
* Return Heap Size
*/
int BinaryHeap::Size()
{
return heap.size();
}
/*
* Insert Element into a Heap
*/
void BinaryHeap::Insert(int element)
{
heap.push_back(element);
heapifyup(heap.size() -1);
}
/*
* Delete Minimum Element
*/
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;
}
/*
* Extract Minimum Element
*/
int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}
/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector <int>::iterator pos = heap.begin();
cout<<\"Heap --> \";
while (pos != heap.end())
{
cout<<*pos<<\" \";
pos++;
}
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])
{
int 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)
{
int 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.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;
}
