min-heap
A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
In more detail
The smallest item can be read instantly, and adding or removing an item takes logarithmic time, because only one path through the tree has to be reordered. Priority queues are usually built on a heap, which is how Dijkstra's and Prim's algorithms fetch the cheapest option next and how timer systems find the timer that expires first.
Example
libuv stores every active timer in a min-heap, so each event loop turn only checks the root to know whether any timer is due.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.
- 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.
- data structure — A way of arranging data in memory, such as a list, dictionary, tree or graph, so that certain operations become cheap.
- logarithmic time — Work that grows by only one step each time the input doubles, written O(log n), typical of algorithms that halve the problem each step.
- timers phase — The first phase of each event loop turn, which runs the callbacks of setTimeout and setInterval timers that have expired.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Timers Phase: setTimeout, Min-Heap Scheduling & Drift — Node.js Internals & Backend Services
- Poll & Check Phases: I/O Callbacks & setImmediate — Node.js Internals & Backend Services