Priority Queue Implementation using Array

February 8, 2021

Priority Queue using Arrays in Java

Normal queue follows a First In First Out (FIFO) order to insert and remove an element. However, in a priority queue, an item with the highest priority comes out first.

Every element in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. If the two items have same priorities, the order of removal is not defined and depends on implementation.

Let us look into real world example :

Have you ever seen in bank line that the higher priority is given to the disabled person then elderly person then comes normal person .In same way priority queue is functioned .

Types of Priority Queue:

Min Priority Queue: In min priority Queue minimum number of value gets the highest priority and lowest number of element gets the highest priority.
Max Priority Queue: Max priority Queue is where maximum number value gets the highest priority and minimum number of value gets the minimum priority.

Operations on a priority queue

EnQueue: EnQueue operation inserts an item into the queue. The item can be inserted at the end of the queue or at the front of the queue or at the middle. The item must have a priority.
DeQueue: DeQueue operation removes the item with the highest priority from the queue.
Peek: Peek operation reads the item with the highest priority.

Priority Queue Implementation

Priority Queue can be impleted in two ways:

Using ordered Array: In ordered array insertion or enqueue operation takes O(n) time complexity because it enters elements in sorted order in queue. And deletion takes O(1) time complexity.
Using unordered Array: In unordered array deletion takes O(n) time complexity because it search for the element in Queue for the deletion and enqueue takes o(1) time complexity.

ALGORITHM:

Insertion

Ask the data and its priority from the user.
Insert the data in the queue before at the position where given priority is greater then priority of the element in queue.

Deletion

Remove the element and the priority from the front of the queue.

Print

Using loop take the starting point from the front of the queue and ending point from the rear of the queue and print the data.

JAVA CODE :

// Java program to show working of PriorityQueue 

import java.util.*; 

class prepinsta{ 
    public static void main(String args[]) 
    { 
        
        PriorityQueue<Integer> pQueue = 
            new PriorityQueue<Integer>(Collections.reverseOrder()); 

        // Adding items to the pQueue using add() 
        pQueue.add(80); 
        pQueue.add(60); 
        pQueue.add(40); 
        pQueue.add(20); 

        // Printing the most priority element 
        System.out.println(“Head value is:” + 
                                            pQueue.peek()); 

        // Printing all elements 
        System.out.println(“The queue elements:”); 
        Iterator itr = pQueue.iterator(); 
        while (itr.hasNext()) 
            System.out.println(itr.next()); 

        // Removing the top priority element (or head) and 
        
        pQueue.poll(); 
        System.out.println(“After removing an element “
                        + “with poll function:”); 
        Iterator<Integer> itr2 = pQueue.iterator(); 
        while (itr2.hasNext()) 
            System.out.println(itr2.next()); 

        // Removing 60 using remove() 
        pQueue.remove(60); 
        System.out.println(“after removing 60 with”
                        + ” remove function:”); 
        Iterator<Integer> itr3 = pQueue.iterator(); 
        while (itr3.hasNext()) 
            System.out.println(itr3.next()); 

        
        Object[] arr = pQueue.toArray(); 
        System.out.println(“Value in array: “); 
        for (int i = 0; i < arr.length; i++) 
            System.out.println(“Value: “ + arr[i].toString()); 
    } 
} 

Output:

Head value is:80  The queue elements: 80 60 40 20
After removing an element with poll function: 60 40
20
after removing 60 with remove function: 40 20  Value in array: 
Value: 20
Value: 10