Question

Write Binary Heap program in C++. And Insert E,H,I,D,G,F,A,B,C. Then, use reheapup algorithm and print out the result.

Need to use this algorithm.

ReheapUp ( int root, int bottom )

// Pre: bottom is the index of the node that may violate the heap

// order property. The order property is satisfied from root to

// next-to-last node.

// Post: Heap order property is restored between root and bottom

{

    int parent ;

    if ( bottom > root )

    {

parent = ( bottom - 1 ) / 2;

if ( elements [ parent ] < elements [ bottom ] )

{

   Swap ( elements [ parent ], elements [ bottom ] );

   ReheapUp ( root, parent );

}

    }

}

Answer 1

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

void Swap(char &x, char &y)
{
   char tmp = x;
   x = y;
   y = tmp;
}

// Inside the class ReheapUp is the same function as the ReheapUp.
// I know it looks different but you can check that they are performing the same operation.

/*
* Class for BinaryHeap
*/
class BinaryHeap
{
private:
  
int left(int parent);
int right(int parent);
int parent(int child);
void ReheapUp(int index);
public:
       vector <char> heap;
BinaryHeap(){}
void Insert(char data);
void DisplayHeap();
int Size();
};

int BinaryHeap::Size()
{
/**
Returns size of the heap
*/
return heap.size();
}

void BinaryHeap::Insert(char data)
{
/*
* Function to Insert Element into the Heap
*/
heap.push_back(data);
   ReheapUp(heap.size() -1);
}

/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector <char>::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;
}

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

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

void BinaryHeap::ReheapUp(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] < heap[in])
{
char tmp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = tmp;
ReheapUp(parent(in));
}
}


int main()
{
BinaryHeap h;
while (1)
{
  
cout<<"1.Insert Element"<<endl;
cout<<"2.Print Heap"<<endl;
cout<<"3.Exit"<<endl;
int choice;
       char data;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the data to be inserted: ";
cin>>data;
h.Insert(data);
break;
case 2:
cout<<"Displaying elements of Heap: ";
h.DisplayHeap();
break;
case 3:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}

P-T3TOJFP:/mnt/g/HomeworkLib/c++ noorul-hasan DESKTOP-T3TeOFP: noorul-hasan DESKTOP-T3TeFP: 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: E 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: H 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: I 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: D 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: G 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: F 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: A 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: B 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 $ g++ BinaryHeap.cpp $./a.out

d noorul-hasan@DESKTOP-T3TOJFP:/mnt/g/HomeworkLib/c++ 3.Exit Enter your choice: 1 Enter the data to be inserted: D 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: G 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: F 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: A 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: B 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 1 Enter the data to be inserted: C 1.Insert Element 2.Print Heap 3.Exit Enter your choice: Displaying elements of Heap: Heap - IGHDEFABC 1.Insert Element 2.Print Heap 3.Exit Enter your choice: 3 noorul-hasan@DE SKTOP-T3T8JFP:/п 2