---
description: >-
  A priority queue is a special type of queue in data structure where each
  element is associated with a priority.
---

# What's Priority Queue & Implementation

{% file src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FDhHWBriZI6i7ZYaVrnd0%2FPriorityQueues.pdf?alt=media&token=dc42ea28-3faf-4050-af00-14698c2b47ad" %}

<mark style="color:blue;">Randomized queue</mark>. Remove a random item.&#x20;

<mark style="color:blue;">Priority queue.</mark> Remove the largest (or smallest) item.

| operation                                  | arguments | return value                      |
| ------------------------------------------ | --------- | --------------------------------- |
| insert                                     | P         |                                   |
| insert                                     | Q         |                                   |
| insert                                     | E         |                                   |
| <mark style="color:red;">remove max</mark> |           | <mark style="color:red;">Q</mark> |
| insert                                     | X         |                                   |
| insert                                     | A         |                                   |
| insert                                     | M         |                                   |
| <mark style="color:red;">remove max</mark> |           | <mark style="color:red;">X</mark> |
| insert                                     | P         |                                   |
| insert                                     | L         |                                   |
| insert                                     | E         |                                   |
| <mark style="color:red;">remove max</mark> |           | <mark style="color:red;">P</mark> |

## Priority Queue Applications

* Event-driven simulation. \[customers in a line, colliding particles]
* Numerical computation. \[reducing roundoff error]
* Data compression. \[Huffman codes]
* Graph searching. \[Dijkstra's algorithm, Prim's algorithm]
* Number theory. \[sum of powers]
* Artificial intelligence. \[A\* search]
* Statistics. \[maintain largest M values in a sequence]
* Operating systems. \[load balancing, interrupt handling]
* Discrete optimization. \[bin packing, scheduling]
* Spam filtering. \[Bayesian spam filter]

## Priority queue client example

<mark style="color:blue;">**Challenge**</mark> Find the largest _<mark style="color:red;">M</mark>_ items in a stream of _<mark style="color:red;">N</mark>_ items. \[N huge, M large]

・Fraud detection: isolate \$$ transactions.&#x20;

・File maintenance: find the biggest files or directories.

{% hint style="info" %}
<mark style="color:blue;">**Constraint**</mark> Not enough memory to store _N_ items. &#x20;

Slides # 6, 7, 8
{% endhint %}

## [Exercise](https://algs4.cs.princeton.edu/24pq/)
