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

Taught in

References