Heap / Priority Queue

Maintain partial ordering so the minimum or maximum element is accessible in O(1) and inserts/removals cost O(log n).

Maintain partial ordering so the minimum or maximum element is accessible in O(1) and inserts/removals cost O(log n).

The root always holds the current minimum (min-heap) or maximum (max-heap) across all elements currently in the heap.

A binary heap enforces the heap property in O(log n) per insert/extract, making repeated extremum extraction far cheaper than full sorting.

For Top-K problems, a fixed-size heap of K elements avoids storing all n elements.