Implement a max priority queue in java that maintains the following properties:1
ID: 3721512 • Letter: I
Question
Implement a max priority queue in java that maintains the following properties:1) At any time, with the max priority is kept at the top. 2) At any time, the priority of a parent node is higher than the priority of its children.
Implement the following methods:
// count how many items present in priority queue
// return the integer count
// O(1)
public int size();
// return the top item (of the max priority) in the priority queue
// return null if empty
// O(1)
public T peek();
// remove the top item (of the max priority) from the priority queue
// return that item to be deleted
// return null if empty
// O(logN): N is the number of items in priority queue
public T remove();
// add an item v with priority p into the priority queue
// no checking whether a duplicate value is already in queue
// return: nothing
// O(logN): N is the number of items in priority queue
public void insert(T v, int p);
// perform a priority update for items in the priority queue based on the following rules
// - If the item is the same as v: set the priority as p
// - If the item is different from v, compare their priorities
// - For any item x with a priority <= v's priority, decrement x's priority by 1
// - Otherwise, do not change x's priority
//
// Hint: perform necessary adjustment to ensure a valid priority queue after updating
// O(N): N is the number of items in priority queue
public void updatePriority(T v, int p);
// check whether there is a value v associated with priority p in the priority queue
// return true if present
// return false otherwise
// O(N): N is the number of items in priority queue
public boolean contains(T v, int p);
Explanation / Answer
/**
** Java Program to implement Priority Queue
**/
import java.util.Scanner;
/** class Task **/
class Task
{
String job;
int priority;
/** Constructor **/
public Task(String job, int priority)
{
this.job = job;
this.priority = priority;
}
/** toString() **/
public String toString()
{
return "Job Name : "+ job +" Priority : "+ priority;
}
}
/** Class PriorityQueue **/
class PriorityQueue
{
private Task[] heap;
private int heapSize, capacity;
/** Constructor **/
public PriorityQueue(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
/** function to clear **/
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
/** function to check if empty **/
public boolean isEmpty()
{
return heapSize == 0;
}
/** function to check if full **/
public boolean isFull()
{
return heapSize == capacity - 1;
}
/** function to get Size **/
public int size()
{
return heapSize;
}
/** function to insert task **/
public void insert(String job, int priority)
{
Task newJob = new Task(job, priority);
heap[++heapSize] = newJob;
int pos = heapSize;
while (pos != 1 && newJob.priority > heap[pos/2].priority)
{
heap[pos] = heap[pos/2];
pos /=2;
}
heap[pos] = newJob;
}
/** function to remove task **/
public Task remove()
{
int parent, child;
Task item, temp;
if (isEmpty() )
{
System.out.println("Heap is empty");
return null;
}
item = heap[1];
temp = heap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heap[child].priority < heap[child + 1].priority)
child++;
if (temp.priority >= heap[child].priority)
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
}
/** Class PriorityQueueTest **/
public class PriorityQueueTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Priority Queue Test ");
System.out.println("Enter size of priority queue ");
PriorityQueue pq = new PriorityQueue(scan.nextInt() );
char ch;
/* Perform Priority Queue operations */
do
{
System.out.println(" Priority Queue Operations ");
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. check empty");
System.out.println("4. check full");
System.out.println("5. clear");
System.out.println("6. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter job name and priority");
pq.insert(scan.next(), scan.nextInt() );
break;
case 2 :
System.out.println(" Job removed "+ pq.remove());
break;
case 3 :
System.out.println(" Empty Status : "+ pq.isEmpty() );
break;
case 4 :
System.out.println(" Full Status : "+ pq.isFull() );
break;
case 5 :
System.out.println(" Priority Queue Cleared");
pq.clear();
break;
case 6 :
System.out.println(" Size = "+ pq.size() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.