Can you design a priority queue?

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority level. If elements with the same priority occur, they are served according to their order in the queue.

Here’s a design for a basic priority queue using a binary heap. Keep in mind that there are several possible ways to implement a priority queue, and the best method depends on the specific requirements of your problem. This method has an average time complexity of O(log n) for insertions and deletions, and O(n) for building the initial queue from an array of items.

Here’s the priority queue class:

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def is_empty(self):
        return len(self.heap) == 0

    def push(self, priority, item):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        _, item = heapq.heappop(self.heap)
        return item

    def peek(self):
        return self.heap[0][1]

In this class, ‘push‘ method inserts an item into the queue by appending it to end and reorders the heap to maintain the heap property. ‘pop‘ method deletes the root from the heap, reorders the heap, and returns the item associated with the previous root. ‘peek‘ method gives the highest priority element but does not modify the heap.

This PriorityQueue class is a binary min heap - the parent node is less than or equal to its children. An element with high priority is considered to have low value and is therefore given precedence.

Now, you want to use it:

priority_queue = PriorityQueue()

# inserting elements into the priority queue
priority_queue.push(3, "Apple")
priority_queue.push(1, "Banana")
priority_queue.push(2, "Cherry")

# removing elements from the priority queue
print(priority_queue.pop())  # Outputs: Banana
print(priority_queue.pop())  # Outputs: Cherry
print(priority_queue.pop())  # Outputs: Apple

Here, the elements are served according to their priority. Since 1 has the highest priority, "Banana" is served first, then "Cherry" with the second highest priority (2), and finally "Apple" with the lowest priority (3).

This example follows Python’s standard library ‘heapq‘ which provides functions for creating min heap. If you want to create a max heap, you can simply invert the values or priorities.

And, as always, it’s good to add error checking in production-level code (for example, checking that the queue isn’t empty before popping).

This structure can be visualized in the form of a binary tree or a heap tree for better understanding.

If you want more advanced features like searching for or removing arbitrary elements, you could use a more complex data structure such as a balanced binary search tree or a Fibonacci heap. But these are much more complex to implement and understand, and typically have slower average-case performance for a basic priority queue.