8 has a priority lower than 5 so we traverse the linked list till we find a position where it is suitable. Let us consider that we need to insert an element with priority 8. Hence, the worst time complexity is O(n) as the worst case is when all elements of the list need to be traversed.įor example, let us consider the linked list: To insert an element, the list is traversed until a suitable position is found for the element to be inserted in order to maintain the overall order of the linked list.

Then, based on priority, all the elements in the list are arranged in descending order based on priority. In the linked list, the element having higher priority will be present at the head of the list.

Implementation of Priority Queue in Data StructuresĪ Priority Queue is implemented using one of the 4 Data Structures: 1. On the other hand, 1 is the smallest number and is hence the item with the lowest priority. In this priority queue, 8 is the largest number and is hence the item with the highest priority. The first step would be to arrange them in descending order as follows: The larger the element(number), the higher the priority. In a descending order priority queue, all the elements are compared with another and the rule: On the other hand, 8 is the largest number and is hence the item with the lowest priority. In this priority queue, 1 is the smallest number and is hence the item with the highest priority. The first step would be to arrange them in ascending order as follows: Let us consider a priority queue having the following priorities: The smaller the element(number), the higher the priority is applied. In an ascending order priority queue, all the elements are compared with another and the rule: the element that entered the priority queue first will be the first to be removed.Īs mentioned before, the elements in the priority queue must be comparable which means they are either less than, equal to or greater than one another.

If two elements in the queue have the same priority value then the first in first out rule is followed for these two elements alone i.e.

Higher or lower priority elements must be dequeued before lower or higher priority elements respectively depending on priority order taken by user that is if user consider lower number as higher priority or higher number as higher priority.

Each item in the queue must have a priority associated with it.

Characteristics of a Priority QueueĪ queue is called a Priority Queue when it has the following characteristics: (in such a way that the highest priority elements are moved to the beginning of the queue and the lowest priority elements are moved to the back of the queue). Hence, the items in the priority queue are arranged in either ascending or descending order depending on the priority value taken by the user.

However, in a Priority Queue, each item in the queue is assigned a priority, and items are dequeued or removed based on this priority value assigned to them. Just like any queue we form, the person that stands first in the queue, will be addressed first and similarly, even in computer science queues, the same rule applies. In a normal Queue, first-in-first-out is followed which means that whichever elements enters the queue first, will be the first to leave. It is an Abstract Data Type that functions a little differently than a normal Queue. if the two elements are a and b, they should follow one of the conditions:Īs a result, the items in the priority queue are arranged in ascending or descending order. Elements are called comparable if they are either lesser than, equal to or greater than one another, i.e. It is important to note that a priority queue only supports elements that are comparable. Operating System, due on Friday Priority Number 4.Data Structures and Algorithms, due on Wednesday Priority Number 2.Statistics, due on Tuesday Priority Number 1.Database Management Systems, due on Thursday Priority Number 3.So instead, you assign a priority to each of them and get them done in that order. Data Structures and Algorithms, due on WednesdayĪs a student, overburdened with work, if you do first come, first serve, you might not be able to submit all your assignments on time.

Database Management Systems, due on Thursday.Deletion : O ( l o g n ) O(log n) O ( l o g n )Ĭonsider a situation where you have 4 assignments, as of Monday:.Insertion : O ( l o g n ) O(log n) O ( l o g n ).That is, higher priority elements are served first. And, elements are served on the basis of their priority. A priority queue is a special type of queue in which each element is associated with a priority value.

Python priority queue instead of sort