Priority Queue in Python

  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.

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.

For insertion, the priority queue uses the put function in the following way:

    p.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(1)

q.put(5)

while not q.empty():

            next_item=q.get()
            print(next_item)

Output- 

1 2 3 4 5                   

Read More

Merge k Sorted Lists- Difficulty [HARD] - Time Complexity- O(N log N) and Space Complexity- O(N)

 

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

Read More