o do: Java You will create a Priority Queue using a Heap represented in an array

ID: 3807012 • Letter: O

Question

o 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 Expert Answer

Explanation / Answer

import java.util*;

import java.io*;

public class Heap<extends Comparable<T>>

{

ArrayList<Integer> arr[25];

HashMap<Integer, Integer> hash;

int N;

public Heap()

{

arr = new ArrayList<Integer>();

hash = new HashMap<Integer, Integer>();

}

public void insert(int x)

{

if (hash.get(x) != null)

return;

int s = arr.size();

arr.add(x);

hash.put(x,s);

}

public T remove()

{

if (isEmpty()) return null;

T t= arr[1];

exch(1,N--);

arr[N+1] = null;

sink(1);

if (N == (arr.length -1)/4) resize((arr.length-1) / 2 + 1);

return t;

hash.put( last, t);

}

struct node

{ int data;

struct node* left, *right;

};

void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for (i=1; i<=h; i++)
printGivenLevel(root, i);
}

void printGivenLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}

public Heap()

{

arr =(T[])new Comparable [2];

N=0;

}

public String toString()

{ StringBuffer Sb= new StringBuffer();

for(int i=1; i<=N; i++)

{ sb.append(arr[i].toString()+"");

return sb.toString();

}

private void resize(int capacity)

{

T[] copy = (T[]) new Comparable[capacity];

for(int i = 1; i <= N; i ++ )

copy[i] = arr[i];

arr = copy;

}

private void swim(int k){

while(k > 1 && less(k/2, k)){

exch(k/2,k);

k = k/2;

}

private void sink(int k)

{

while (2*k < N)

{

int j = 2 * k;

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

if(less(j, k)) break;

exch(k,j);

k = j;

}

Class Main()

{

public static void main(String args[])

{ Heap ab = new Heap();

ab.insert(15);