priority queue

A collection where each item has a priority and the item removed next is always the one with the highest priority, not the oldest.

In more detail

A binary heap implements it with O(log n) insert and remove. Task schedulers, event simulators, Dijkstra's algorithm, Prim's algorithm and Huffman coding all rely on one. In Python, push (priority, counter, item) tuples onto a heapq list.

Related terms

Taught in

References