JAVA

Develop a max-value priority Queue utilizing the results from Question 1. Max-value priority queues are queues in which you can insert values as in normal queues but you have to maintain heap order at all times. You can only remove/delete the maximum value from priority Queue.

Notice: be careful about overflows and underflows.

Here is the Question 1 code:

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class MaxHeap

{

//declaring Heap

private int size;

private int maxsize= 10000;

private int[] Heap = new int[maxsize + 1];

//making heap by passing an array

public MaxHeap(int siz,int a[])

{

int i;

//this.maxsize = maxsize;

this.size = 0;

Heap[0] = Integer.MAX_VALUE;

for(i=1;i<=siz;i++){

Heap[i]=a[i];

this.size++;

}

maxHeap();

}

public void maxHeap()

{

for (int pos = size; pos >= 1; pos--)

{

//System.out.println(size);

maxHeapify(pos);

}

}

private boolean isLeaf(int x)

{

if (x >= (size / 2) && x <= size)

{

return true;

}

return false;

}

//Function used to create a Heap

private void maxHeapify(int pos)

{

//System.out.println(pos);

if(rightChild(pos)<=size){

if ( Heap[pos] < Heap[leftChild(pos)] || Heap[pos] < Heap[rightChild(pos)])

{

if (Heap[leftChild(pos)] > Heap[rightChild(pos)])

{

swap(pos, leftChild(pos));

maxHeapify(leftChild(pos));

}else

{

swap(pos, rightChild(pos));

maxHeapify(rightChild(pos));

}

}

}

else{

if ( leftChild(pos)<=size&& Heap[pos] < Heap[leftChild(pos)])

{

swap(pos, leftChild(pos));

maxHeapify(leftChild(pos));

}

}

}

// return position of parent

private int parent(int x)

{

return x / 2;

}

//return position of leftchild

private int leftChild(int x)

{

return (2 * x);

}

// return position of rightChild

private int rightChild(int x)

{

return (2 * x) + 1;

}

private void swap(int fpos,int spos)

{

int tmp;

tmp = Heap[fpos];

Heap[fpos] = Heap[spos];

Heap[spos] = tmp;

}

// Insert a new element in heap

public void insert(int key)

{

Heap[++size] = key;

int current = size;

while(Heap[current] > Heap[parent(current)])

{

swap(current,parent(current));

current = parent(current);

}

}

public void delete(int key)

{

int i;

for( i=1;i<=size;i++)

{

if(Heap[i]== key){

int popped = Heap[i];

Heap[i] = Heap[size--];

maxHeapify(i);

break;

}

}

if(i>size)

System.out.println("The key is not present in heap ");

}

public void print()

{

for (int i = 1; i <= size / 2; i++ )

{

System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]

+ " RIGHT CHILD :" + Heap[2 * i + 1]);

System.out.println();

}

}

//Used in extracting the maximum element in heap

public int extractmax()

{

int popped = Heap[1];

Heap[1] = Heap[size];

//System.out.print(Heap[size]);

size--;

maxHeapify(1);

return popped;

}

public static void main(String[] arg)

{

int N,i;

Scanner s=new Scanner(System.in);

System.out.println("Enter N: ");

N= s.nextInt();

System.out.println("Enter array: ");

int array[]=new int[N+1];

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

array[i]= s.nextInt();

}

MaxHeap maxHeap = new MaxHeap(N,array);

System.out.println("The Max Heap for given array is");

maxHeap.print();

System.out.println("The max val is " + maxHeap.extractmax() + " ");

System.out.println("The Max Heap after insertion of elements 12,35,23 is ");

maxHeap.insert(12);

maxHeap.insert(35);

maxHeap.insert(23);

maxHeap.print();

System.out.println("The max val is " + maxHeap.extractmax() + " ");

maxHeap.delete(12);

System.out.println("The Max Heap after deletion of element 12 is ");

maxHeap.print();

System.out.println("The max val is " + maxHeap.extractmax() + " ");

}

}