Question

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:

b. What is the Big-Oh running time for insert?

c. Write an implementation that uses these algorithms.

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++;

Answer 1

Complexity of insert is O(n). Since we have to find position of element by traversing the whole array

Minimum: 0 Minimum: 1 Minimum: 2 Minimum: 5

Code

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;i<cap;i++){

                newpr[i] = priority[i];

                newdata[i] = data[i];

            }

            data=newdata;

            priority=newpr;

            cap*=2;

        }

        int pos=0;

        while(pos<size && data[pos]>k){

            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--;

    }

}