How to quickly implement a priority queue?

general
, ,
1

I am looking for quick ways of implementing a priority queue, for the use of Dijkstra and Prim’s algorithm. I am not looking for implementations of priority queue from the standard library as there is none that I know of in my programming language.

Please have answer in pseudo-code! Ty

2

Implement heap :wink:

3

how long does it take to implement a priority queue on heap? I programmed one and it took me 30-50 minutes to code. I’m not looking for an efficient implementation but an implementation that can be implemented quickly.

4

If you are using c++ there is an in built container priority_queue ( http://www.cplusplus.com/reference/queue/priority_queue/ ).

5

there’s a priority queue in java

PriorityQueue< Long > abc=new PriorityQueue< Long >();

I would say this can be implemented pretty quickly :wink:

6

Here’s the JAVA code for an Integer Priority Queue. However, you can translate it into your language since the most complex aspect of it is an array. This constructor method might be different in your language, but I’m sure it can easily be accommodated for. Also, it doesn’t necessarily have to be an Integer Priority Queue, it could be of any type.

class IntegerPriorityQueue {
    int[] pq; // Array that contains the queue.
    int N;       // Number of elements in pq.

    // Constructor method to initialize the queue.
    public IntegerPriorityQueue( int capacity ) {
        pq = new int[ capacity ]; // Initializes the queue with maximum capacity.
    }

    // Checks if the queue is empty.
    public boolean isEmpty() {
        if( N == 0 )
           return true;
        else
           return false;
    }

    // Inserts element into the queue.
    public void insert( int x ) {

        N = N + 1;
        pq[ N ] = x;

    }

    // Delete the maximum value in the queue.
    public int delMax() {

        int max = 0;
        // Search the queue to find the index of the max value.
        for( int i = 1; i < N; i++ ) {
             if( max < i ) {
                max = i;
              }
         }
         // Swaps the maximum element with the rightmost element.
         int temp = pq[ N - 1 ]; 
         pq[ N - 1 ] = pq[ max ];
         pq[ max ] = temp;

         // Returns the largest element.
         return pq[ --N ];

      }
   }
7

this is my code for implementation of priority queue…
i used array ds to implement priority queue…

#include
using namespace std;
#define MAX 110
static int a[MAX],n;
void construct(int b[],int m)
{ int i;
for(i=0;i<m;i++)
a[i]=b[i];
n=i;
}
void insert(int v)
{ a[n++]=v;
}

int remove()
{ int j,max,v;
max=0;
for(j=1;j<n;j++)
if(a[j]>a[max])
max=j;
v=a[max];
a[max]=a[n–];
return v;
}

int main()
{ int b[]={2,4,6,8,1,0};
  construct(b,6);
  insert(10);
   insert(15);
   insert(30);
   cout<<remove()<<" ";
}