Priority Queue

Intro

Priority queue is an abstract data type. It supports actions like insert, find min, and delete min.

Here is a funny example from ADM: Single people maintain a priority queue of potential dating candidates—mentally if not explicitly. One’s impression on meeting a new person maps directly to an attractiveness or desirability score. Desirability serves as the key field for inserting this new entry into the “little black book” priority queue data structure. Dating is the process of extracting the most desirable person from the data structure (Find- Maximum), spending an evening to evaluate them better, and then reinserting them into the priority queue with a possibly revised score.

Heap

We can implement priority queue in different ways. One maximally efficient implementation is heap. Heap is a type of binary tree.

Questions

lc heap

References

UW-Madison CS367 Lecture 24 Heaps and Priority Queues

The Algorithm Design Manual Ch3.5 Priority Queue

9ch video

Heap and Heapsort by stoimen