Need help with a C++ program invoving heaps along with the analysis questions nt

Question

Need help with a C++ program invoving heaps along with the analysis questions

ntroduction Heaps are commonly referred to as priority queues. The reason is because all elements in the heap are organized relative to a given heap order property. This property requires that items retrieved from the heap is either the smallest value in the heap (called a min heap), or the largest value in the heap called a max heap). In other words, when retrieving data from a min heap, the element with the smallest value over all elements in the heap has priority and is removed first; the same holds for a max heap. The heap data structure is a complete binary tree, implemented as a static or dynamic array, where each subtree i he tree also follow the heap order property (i.e. the root is either the minimal or maximal value in that subtree) Objective To gain experience implementing a heap using an array based binary tree, learn how use the STL vector container, learn how to sort values using heap sort. operations performed upon the heap Since the heap is implemented as an array-based complete binary tree, traversing the tree can be done by simply calculating the index of the next node (or element) to traverse to (or move). How the tree i indexed has been discussed in lecture and is also provided in your text book and the tree lecture slides. Most of the heap operations function were discussed class (and slides) so the below paragraphs will rovide a brief overview: it is assumed that you were present and paid attention in class enqueue: Adds/inserts an item to the heap. An item added to the heap is positioned as the last element of the array at location heapsize 1, where heapsize is the number of elements in the array It the performs the bubble-up operation on that new item. During bubble-up, the newly added item is checked to see if it, at its current position, meets the heap order property when compared to its parent. If it does not, the bubble-up operation moves the new item up the tree until it is in a position that meets the heap order property. Bubble-up can be done iterative or recursively dequeue: Removes/Deletes an item from the heap. Deletions from the heap removes the root from the tree where the root is the first element in the arra the element is either element zero or one depending y, on how the array is indexed. After removing the root, the last element in the heap is moved (i.e., a simple assignment operation) to the array location of the former root and then the bubble-down operation ISS performed on the "new root". The bubble-down operation checks if the "new root" meets the heap order property by comparing it with the value of its children. If it does not, bubble-do wi move the "new root" down the tree until it is in a position that meets the heap order property. Otherwise, if the "new root" meets the heap-order property, bubble-down isn't performed build heap: Builds a heap from a populated array. Build heap is an iterative process that starts at the size/2l, assuming root is at 1) and iterates up to the root center of the tree (the node at index node. At each iteration (i de), it executes the bubble do process starting at the array element of its current position nstructions Your assignment is to write a dynamic array-based Heap class. Your Heap class will support both a min heap structure and a max-heap structure, specified by passing a Boolean argument to the constructor at the creation of a Heap object. Since this is an array-based heap, the "node data" is the priority. You are to implement three operations described above and all other methods specified in the below UML.

Explanation / Answer

#include <iostream>
#include <cstdlib>
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::bubbleup(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::bubbledown(int in)
{

int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0 && heap[in] > heap[child])
{
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;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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