Written in Java

By maintaining the invariant that the elements in the priority queue are sorted in non-increasing order (that is, the largest item is first, the smallest is last), you can implement both findMin and delete Min in constant time. However, insert is expensive. Do the following: c. Write an implementation that uses these algorithms.

My Big O notation

public class Temp { public static void main(String[] args) { PriorityQueue q = new PriorityQueue(); q.insert(1, 3); q.insert(2, 5); q.insert(5, 1); q.insert(0, 2); System.out.println("Minimum: "+q.findmin()); q.deleteMin(); System.out.println("Minimum: "+q.findmin()); q.deleteMin(); System.out.println("Minimum: "+q.findmin()); q.deleteMin(); System.out.println("Minimum: "+q.findmin()); } } class PriorityQueue{ int []priority; int[]data; int cap, size; PriorityQueue(){ priority=new int[10]; data = new int[10]; size=0; cap=10; } PriorityQueue(int cap){ this.cap=cap; size=0; priority=new int[cap]; data = new int[cap]; } void insert(int k, int p){ if(size==cap){ int []newpr=new int[2*cap]; int []newdata=new int[2*cap]; for(int i=0;ik){ pos++; } for(int j=size;j>pos;j--){ priority[j]=priority[j-1]; data[j]=data[j-1]; } data[pos]=k; priority[pos]=p; size++; } int findmin(){ return size>0?data[size-1]:-1; } void deleteMin(){ if(size>0) size--; } }

Algorithm insert": l/Algorithm insert insert(key, priority) //Check condition if (size == Capacity) //Call the method grow() grow(2 * Capacity + 1); // Add data Data.add(key); I/Add priority Priorities[size] = priority; [/Call the method heapifyUp() heapifyUp(size); //Increment the size size++; Algorithm findMin ": //Algorithm find Min find Min() //Check condition if (size() > 0) // Return return Data.get(size-1); //Throw exception throw new No SuchElementException(); Algorithm delete Min ": l/Algorithm delete Min delete Min() //Remove the last data Data.remove(size-1); //Decrement size size--; Algorithm insert": l/Algorithm insert insert(key, priority) //Check condition if (size == Capacity) //Call the method grow() grow(2 * Capacity + 1); // Add data Data.add(key); I/Add priority Priorities[size] = priority; [/Call the method heapifyUp() heapifyUp(size); //Increment the size size++; Algorithm findMin ": //Algorithm find Min find Min() //Check condition if (size() > 0) // Return return Data.get(size-1); //Throw exception throw new No SuchElementException(); Algorithm delete Min ": l/Algorithm delete Min delete Min() //Remove the last data Data.remove(size-1); //Decrement size size