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
- binary heap — A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers