Priority Queue Implementation using Array
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
- 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.
Circular Queue using Linked Lists
Priority Queue using Linked List
Priority Queue Insertion and Deletion
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.
- 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
import java.util.*; class Main{ public static void main(String args[]) { PriorityQueuepQueue = 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
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
- Circular queue in Data Structure
Click Here - Applications of Circular Queues
Click Here - Circular queue in –
C | C++ | Java - Circular queue using Array –
C | C++ | Java - Circular Queue using Linked Lists –
C | C++ | Java
Priority Queue
Stacks
- Introduction to Stack in Data Structure
- Operations on a Stack
- Stack: Infix, Prefix and Postfix conversions
- 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)
- Queues Program in C and implementation
- Implementation of Queues using Arrays | C Program
- Types of Queues in Data Structure
- Application of Queue Data Structure
- 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
- Circular queue in Data Structure
- Applications of Circular Queues
- Circular queue in – C | C++ | Java
- Circular queue using Array – C | C++ | Java
- Circular Queue using Linked Lists – C | C++ | Java
Login/Signup to comment