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.
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.
- 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.
- 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 :
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