# Priority Queue

## Quick reference

Binary Heap Priority Queue

This is the most common implementation but not the only one.

Worst Case
space
peek
dequeue
enqueue

A priority queue is a special queue where:

1. Every item in the queue has a priority, and
2. Higher-priority items are dequeued before lower-priority items.

Picture a big list of bugs for an engineering team to tackle. You want to keep the highest-priority bugs at the top of the list.

#### Strengths:

• Quickly access the highest-priority item. Priority queues allow you to peek at the top item in while keeping other operations relatively cheap ().

#### Uses

• Any time you want to handle things with different priority levels: triaging patients in a hospital, locating the closest available taxi, or just a to-do list.
• Operating system schedulers may use priority queues to select the next process to run, ensuring high-priority tasks run before low-priority ones.
• Certain foundational algorithms rely on priority queues:
• Dijkstra's shortest-path
• A* search (a graph traversal algorithm like BFS)
• Huffman codes (an encoding for data compression)

## Implementation

### Binary Heaps

Priority queues are often implemented using binary heaps. Notice how the highest priority is right at the top of the heap, ready to be grabbed in time.

• To enqueue an item, add it to the heap using the priority as the key. ( time)
• To peek at the highest priority item, look at the item at the top. ( time)
• To dequeue the highest priority item, remove the top item from the heap. ( time)

### Other Options

#### A Sorted List

• To enqueue, use binary search to figure out where the new item should go. Then scoot items over to make space for the new item. ( time, since in the worst case you have to scoot everything over to make room)
• To peek at the highest priority item, look at the item at index zero. ( time)
• To dequeue, scoot every item forward one index. ( time)

• To enqueue, walk through the linked list to figure out where the new item should go. Then, reassign pointers to add the new item. ( time)
• To peek at the highest priority item, look at the item at the head of the linked list. ( time)
• To dequeue, update the linked list's head pointer to point to the second item. (And deallocate the old head node, if you're using a language with manual memory management.) ( time)

#### Fancier Heaps

Binary heaps are just one kind of heap. Other kinds of heaps (e.g.: Fibonacci heaps or binomial heaps) can offer faster average performance for some priority queue operations. But, they're much more complex than binary heaps and less commonly used in practice.

In a coding interview, you usually can't go wrong by using a binary-heap based priority queue.