26 Algorithms library [algorithms]

A random access range [a, b) is a heap with respect to comp and proj for a comparator and projection comp and proj if its elements are organized such that:

• (1.1)
  With N = b - a, for all i, $0<i<N$, bool(invoke(comp, invoke(proj, a[$\lfloor \frac{i-1}{2}\rfloor$]), invoke(​proj, a[i]))) is false.
• (1.2)
  *a may be removed by pop_heap, or a new element added by push_heap, in $O\left(\log N\right)$ time.

These properties make heaps useful as priority queues.

make_heap converts a range into a heap and sort_heap turns a heap into a sorted sequence.