In this activity you need to modify PQ implementation $($BinaryHeap$.$cpp$)$ to make it based on $3-$way $(3-$children$)$ heap tree. To do so$,$ you need to update swim$-$up and sink$-$down functions.

$3-$way heap is also discussed in the this week's lecture $(21$m:$30$s$).$

After making required modification, demonstrate your new code with the following operations.

$-$ Add $32$ random items to PQ$.$ Each item $($integer$)$ will be randomly selected between $0$ and $100.$

$-$ Show the PQ array. Note that $0$th item of the array is always skipped.

$-$ Repeatedly delete max of PQ $5$ times showing the PQ array.

Expected output of your program will be similar to

PQ created

$75,72,68,73,67,65,61,......$

Delete $75$

$73,72,68,65,67,65,61,......$

Delete $73$

$72,67,68,65,67,65,61,....$

Delete $72$

$.....$

Delete $??$

$....$

Delete $??$

$.....$

Note that there is no user input required for this program

$//$

#include

#include

#include

#include

#include $//$ std::setw

$//$ #define N $10$

using namespace std;

class BinaryHeap

$\{$

public:

BinaryHeap$()$; $//$ Construction

bool less$($int i$,$ int j$)$;

void exch$($int i$,$ int j$)$;

void swim$($int k$)$;

void sink$($int k$)$;

bool isEmpty$()$;

int size$()$;

void insert$($int v$)$;

int delMax$()$;

void ListArray$()$;

void printT$($int x$,$ int id$)$;

private:

int N $=10$;

int $*$pq;

int capacity $=100$;

$\}$;

$//$ Initialize the class

BinaryHeap::BinaryHeap$()$

$\{$

pq $=$ new int$[$capacity$]$;

cout $<<$ "A new priority queue with $"<<$ capacity $<<"$ capacity was created...!" $<<$ endl ;

$\}$

void BinaryHeap::ListArray$()$

$\{$

for $($int i$=1$; i $<=$ N; i$++)//$ Remember we have "size" items

$\{$

cout $<<$ pq$[$i$]<<","$;

$\}$

$\}$

void BinaryHeap::swim$($int k$)$

$\{$

while $($k $>1$ && less$(($k$+1)/3,$ k$))$

$\{$

exch$($k$+1)/3,$ k$)$;

k $=($k$+1)/3$;

$\}$

$\}$

void BinaryHeap::isEmpty$()$

$\{$ return N $==0$; $\}$

int BinaryHeap::size$()$

$\{$ return N; $\}$

void BinaryHeap::insert$($int v$)$

$\{$

pq$[++$N$]=$ v;

swim$($N$)$;

$\}$

int BinaryHeap::delMax$()$

$\{$

int max $=$ pq$[1]$;

exch$(1,$ N$--)$;

pq$[$N$+1]=$ NULL;

sink$(1)$;

return max;

$\}$

void BinaryHeap::sink$($int k$)$

$\{$

while $(2*$k $<=$ N$)$

$\{$

int j $=2*$k;

if $($j $<$ N && less$($j$,$ j$+1))$ j$++$;

if $(!$less$($k$,$ j$))$ break;

exch$($k$,$ j$)$;

k $=$ j;

$\}$

$\}$

bool BinaryHeap::less$($int i$,$ int j$)$

$\{$

if $($pq$[$i$]<$ pq$[$j$])$

return true;

return false;

$\}$

void BinaryHeap::exch$($int i$,$ int j$)$

$\{$

int t $=$ pq$[$i$]$; pq$[$i$]=$ pq$[$j$]$; pq$[$j$]=$ t;

$\}$

$//1->2,3$

$//2->4,5$

$//3->6,7$

void BinaryHeap::printT$($int x$,$ int id$)$

$\{$

if $($x$>$N$)$ return;

printT$(2*$x$+1,$id$+10)$;

cout $<<$ setw$($id$)<<\text{'}\text{'}<<$ pq$[$x$]<<$ endl;

printT$(2*$x$,$id$+10)$;

$\}$

$//$ The program lunches here

int main$()$

$\{$

BinaryHeap BH;

for $($int i$=0$; i $<20$; i$++)$

BH$.$insert$($ rand$()\%50+1)$;

BH$.$ListArray$()$;

cout$<<"------$

$"$;

BH$.$printT$(1,10)$;

$\}$