The **priority queue** is an advanced type of the [queue](https://www.educative.io/answers/what-is-a-queue) data structure. Instead of dequeuing the oldest element, a priority queue sorts and dequeues elements based on their *priorities*. 

Priority queues are used to handle scheduling problems where some tasks are prioritized over others.

# The `queue.PriorityQueue` Class

Python provides a built-in implementation of the priority queue data structure. 

Since the `queue.PriorityQueue` class needs to maintain the order of its elements, a sorting mechanism is required every time a new element is enqueued.

Python solves this by using a *binary heap* to implement the priority queue. 

The Python priority queue is built on the `heapq` module, which is basically a binary [heap](https://www.educative.io/answers/what-is-a-heap).

For insertion, the priority queue uses the `put` function in the following way:
```python
    pQueue.put(value)
```

The `get` command dequeues the highest priority elements from the queue.

from queue import PriorityQueue

q = PriorityQueue()

q.put(4)
q.put(2)
q.put(5)
q.put(1)
q.put(3)

while not q.empty():
    next_item = q.get()
    print(next_item)

Priority-object pairs can also be inserted into the queue. This way every task can be associated with a priority.

from queue import PriorityQueue

q = PriorityQueue()

q.put((4, 'Read'))
q.put((2, 'Play'))
q.put((5, 'Write'))
q.put((1, 'Code'))
q.put((3, 'Study'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# Time complexity
The complexity of the insertion and deletion operations are given below:

| **Operation** | **Worst-case Time Complexity** |
| --- | --- |
| Insertion | *O(logn)* |
| Deletion | *O(logn)* |


What is the Python priority queue?

The priority queue is an advanced type of the queue data structure. Instead of dequeuing the oldest element, a priority queue sorts and dequeues elements based on their priorities. Priority queues are used to handle scheduling problems where some tasks are prioritized over others. The queue.PriorityQueue Class Python provides a built-in implementation of the priority queue data structure. Since the queue.PriorityQueue class needs to maintain the order of its elements, a sorting mechanism is required every time a new element is enqueued. Python solves this by using a binary heap to implement the priority queue. 

Operation	Worst-case Time Complexity
Insertion	O(logn)
Deletion	O(logn)