> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/priority-queue/whats-priority-queue-and-implementation.md).

# What's Priority Queue & Implementation

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

{% file src="/files/LbGxEYAn43rFRIpyWlOn" %}

<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/)