Priority Queue Implementation using Array

priority queue using array in java

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. On this page we will discuss priority queue implementation using array.

Priority Queue Implementation using Array

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.

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

  1. 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.
  2. DeQueue: DeQueue operation removes the item with the highest priority from the queue.
  3. Peek: Peek operation reads the item with the highest priority.
Implementation of Priority Queue using Array

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 to implement priority queue using array

Run
import java.util.*;
class Main{
    public static void main(String args[])
    {

        PriorityQueue pQueue =
                new PriorityQueue(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 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 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
20
40
after removing 60 with remove function:
40
20
Value in array: 
Value:40
Value:20

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java