Priority Queue

Priority Queue

One important variation of a queue is called a priority queue. A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front.

You can probably think of a couple of easy ways to implement a priority queue using sorting functions and lists. However, inserting into a list is 𝑂(𝑛) and sorting a list is 𝑂(𝑛log𝑛). We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in 𝑂(log𝑛).

The binary heap is interesting to study because when we diagram the heap it looks a lot like a tree, but when we implement it we use only a single list as an internal representation. The binary heap has two common variations: the min heap, in which the smallest key is always at the front, and the max heap, in which the largest key value is always at the front. In this section we will implement the min heap. We leave a max heap implementation as an exercise.

Priority Queue in Python

Priority Queue is an extension of the queue with following properties. 1) An element with high priority is dequeued before an element with low priority. 2) If two elements have the same priority, they are served according to their order in the queue.

Below is simple implementation of priority queue.

# A simple implementation of Priority Queue 
# using Queue. 
class PriorityQueue(object): 
    def __init__(self): 
        self.queue = [] 
  
    def __str__(self): 
        return ' '.join([str(i) for i in self.queue]) 
  
    # for checking if the queue is empty 
    def isEmpty(self): 
        return len(self.queue) == [] 
  
    # for inserting an element in the queue 
    def insert(self, data): 
        self.queue.append(data) 
  
    # for popping an element based on Priority 
    def delete(self): 
        try: 
            max = 0
            for i in range(len(self.queue)): 
                if self.queue[i] > self.queue[max]: 
                    max = i 
            item = self.queue[max] 
            del self.queue[max] 
            return item 
        except IndexError: 
            print() 
            exit() 
  
if __name__ == '__main__': 
    myQueue = PriorityQueue() 
    myQueue.insert(12) 
    myQueue.insert(1) 
    myQueue.insert(14) 
    myQueue.insert(7) 
    print(myQueue)             
    while not myQueue.isEmpty(): 
        print(myQueue.delete())  

Output:

12 1 14 7
14
12
7
1
()

Note that the time complexity of delete is O(n) in above code.

heapq - Heap queue algorithm

• heapq.heappush(heap, item)

  • Push the value item onto the heap, maintaining the heap invariant.

• heapq.heappop(heap)

  • Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
• heapq.heapify(x)

  • Transform list x into a heap, in-place, in linear time.

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

LintCode 4.Ugly Number II

from heapq import heappush, heappop


class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        # write your code here
        pq = []
        history = set()
        history.add(1)
        heappush(pq, 1)

        count, res = 0, -1
        while count < n:
            res = heappop(pq)
            count += 1
            nums = [res * 2, res * 3, res * 5]
            for i in nums:
                if i not in history:
                    history.add(i)
                    heappush(pq, i)
        return res

References

1. https://runestone.academy/runestone/static/pythonds/Trees/PriorityQueueswithBinaryHeaps.html
2. https://docs.python.org/2/library/heapq.html
3. https://www.geeksforgeeks.org/priority-queue-in-python/