Problem Statement: Implement $3-$ary heapProblem Statement: Implement $3-$ary heap

In this programming homework, you are required to write a program in either C$++$ or Java that

can perform basic operations on a $3-$ary heap. Unlike a binary heap with $2$ children per node, a

$3-$ary heap has $3$ children per node.

A sample code and$/$or guided pseudocode has been provided herewith. This sample code is for

a binary heap. You task is to complete the commented lines with a "recursive version code".

The file also contains two non$-$recursive functions written at the bottom. These should be used

just as a guideline for filling up the recursive version. Once your recursive version is working,

you should modify it from binary heap to $3-$ary heap. Make sure that you DO NOT CHANGE

the main function.

Required Output:

The output of your code should exactly match the content of the "heap$\_$output.txt$"$ file, with a

newline appended to the last output.

In this programming homework, you are required to write a program in either C$++$ or Java that

can perform basic operations on a $3-$ary heap. Unlike a binary heap with $2$ children per node, a

$3-$ary heap has $3$ children per node.

A sample code and$/$or guided pseudocode has been provided herewith. This sample code is for

a binary heap. You task is to complete the commented lines with a $$recursive version code$.$

The file also contains two non$-$recursive functions written at the bottom. These should be used

just as a guideline for filling up the recursive version. Once your recursive version is working,

you should modify it from binary heap to $3-$ary heap. Make sure that you DO NOT CHANGE

the main function.

Required Output:

The output of your code should exactly match the content of the $$heap$\_$output.txt$$ file, with a

newline appended to the last output.

$```$java

$//$sample code and$/$or guided pseudocode for a binary heap

import java.io$.*$;

import java.util.$*$;

public class Heap

$\{$

int A$[]$; $//$you may use ArrayList instead

int size $=0$;

int max;

public Heap$($int max$)$

$\{$

A $=$ new int$[$max$]$;

this.max $=$ max;

$\}$

int min$($int i$,$ int j$)$

$\{//$returns index of minimum value within A$[$i$..$j$]$

int minindex $=$ i;

for$($int k$=$i$+1$; kj; k$++)$

if $($A$[$k$]$ A$[$minindex$])$ minindex $=$ k;

return minindex;

$\}$

void swap$($int i$,$ int j$)\{$int temp $=$ A$[$i$]$; A$[$i$]=$ A$[$j$]$; A$[$j$]=$ temp;$\}$

public int extractmin$()$

$\{$

if $($size $==0)$ return $-1$; $//$error

int retval $=$ A$[0]$;

A$[0]=$ A$[$size$-1]$; $//$put last element at the top

size$--$;

heapify$(0)$;

return retval;

$\}$

void heapify$($int top$)$

$\{$

if $($top$*2+1>$ size$-1)$ return;

int minChild;

$//$calculate minChild $-$ refer below to non$-$recursive heapify as a guideline

$//$for this block of code

$//$if minchild and top do not conflict then return

$//$else there is violation of value property so "swap$(,)"$;

$//$recurse with minChild $-$ to fix further down

$\}$

void insert$($int newkey$)$

$\{$

if $($size $==$ max$)$ return; $//$error $-$ you may want to throw an exception

A$[$size$]=$ newkey; $//$ add new key at the end of the heap

size$++$; $//$heap$\text{'}$s size grows by one due to this new arrival

int pos $=$ size$-1$; $//$set pos to last items location

percolate$($pos$)$;

$\}$

void percolate$($int pos$)$

$\{//$ fixes upwards recursively

if $($pos return;

$//$calcuate the position of parent of pos

$//$if all fine $($no conflict above$)$ then return

$//$if conflict the swap with parent

$//$recurse $-$ continue percolating upwards starting at parent now

$\}$

void decreasekey$($int pos, int newkey$)$

$\{//$ decreases the key at A$[$pos$]$ to a new value

$//$if newkey is bigger than A$[$pos$]$ nothing to do

$//$else change A$[$pos$]$ to newkey

$//$fix value property

$\}$

public static void main$($String$[]$ args$)$

$\{$

Heap H $=$ new Heap$(100)$;

for $($int i $=10$; i $>0$; i$--)$

H$.$insert$(($i$*3497+379)\%1000)$;

H$.$decreasekey$(9,100)$;

for $($int i $=0$; i $<mtext\; id="EditorElement\_9302189"></mtext><mn\; id="EditorElement\_9302190">1</mn><mn\; id="EditorElement\_9302191">0</mn>$; i$++)$

System.out.println$($H$.$extractmin$())$;

$\}$

$//-----$ non$-$recursive version below $----------$

void insert$\_$nr$($int newkey$)$

$\{$

if $($size $==$ max$)$ return; $//$error $-$ you may want to throw an exception

A$[$size$]=$ newkey; $//$ add new key at the end of the heap

int pos $=$ size;

size$++$;

int parent;

while$($pos $>0)$

$\{$

parent $=($pos$-1)/2$; $//$calcuate the position of parent

if $($A$[$parent A$[$pos$])$ break;$//$if all fine then break the loop

swap$($parent$,$pos$)$; $//$if conflict then swap with parent

pos $=$ parent;

$\}$

$\}$

void heapify$\_$nr$($int top$)$

$\{$

int minChild;

while $($top$*2+1$

$```$

output:

$100$

$349$

$355$

$361$

$367$

$373$

$852$

$858$

$864$

$870$