To do: Java You will create a Priority Queue using a Heap represented in an arra

Question

To do: Java

You will create a Priority Queue using a Heap represented in an array. All was covered in lecture Friday and all the other Stacks and Queues lectures......do not use the Java API for this, implement it yourself just like I did on Friday.

Needed:

You will need a Heap class that will keep the MININUM values as the highest priority that will be removed from the heap first, and the smaller numbers with less priority.

The Heap class will need an instance field array that holds ints, you can just make the array size 25, and we'll make sure we don't go over 25 elements.

The heap class will need a method for inserting items in the heap.

The Heap class will need a method for removing items from the heap.

Both methods will need to handle rearranging the items in the heap.

The Heap class will need a method for printing out the heap level by level.......until you get to a level that starts with a null.

A Driver class that sends in the ints to be stored in the heap.

Implementation, run these steps in order:

Add the following items to your heap: 15, 5, 8, 4, 9, 22, 17, 6, 14

Print Heap (for loop that prints the arrray, in the proper order)

Remove two items from the heap.

Print Heap

Add the following 18, 12

Print Heap

Remove three items from the heap.

Print Heap

Explanation / Answer

import java.io.*;
{
public static void main(String args[])
{
int a[25];
min_heapify m = new min_heapify();
int b[]= s.sortToArray(a);
for(int i=0;i<b.length;i++)
{
System.out.println("sort array is" + b[i]);
}
add a=new add();
int b[]= s.sortToArray(a);
for(int i=0;i<b.length;i++)
{
System.out.println("sort array is" + b[i]);
}
remove r = new remove();
int b[]= s.sortToArray(a);
for(int i=0;i<b.length;i++)
{
System.out.println("sort array is" + b[i]);
}

}
}
void min_heapify (int Arr[ ] , int i, int N)
{
int left = 2*i;
int right = 2*i+1;
int smallest;
if(left <= N and Arr[left] < Arr[ i ] )
smallest = left;
else
smallest = i;
if(right <= N and Arr[right] < Arr[smallest] )
smallest = right;
if(smallest != i)
{
swap (Arr[ i ], Arr[ smallest ]);
min_heapify (Arr, smallest,N);
}
}
void add (int Arr[ ], int val)
{
int length;
length = length + 1;
Arr[ length ] = -1;
increase_val (Arr, length, val);
}
void remove(int Arr[ ], int val)
{
int length;
length = length - 1;
Arr[ length ] = 1;
decrease_val (Arr, length, val);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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