What is a priority queue?

A queue where each element has a priority.

A priority queue is a data structure where each element has a priority and the highest (or lowest) priority element comes out first.

Unlike a regular queue (FIFO), the dequeue order depends on priority. Implemented with a heap, insert and extract are O(log n).

Used in task schedulers, Dijkstra's algorithm and Huffman coding.

Heap-based implementation

A priority queue is most efficiently implemented with a heap. A min-heap keeps the lowest priority at the root; a max-heap the highest.

Insert: add to heap + sift-up, O(log n). Extract: take root + move last to root + sift-down, O(log n).

Peek (look at root) is O(1). This balances against a sorted array.

Write peek(arr). Return the root (smallest). Print 1 with print(peek([1, 3, 2, 5, 4])).

Show example solution

def peek(arr):
    # Return root
    return arr[0]
print(peek([1, 3, 2, 5, 4]))