27
Algorithms library
[algorithms]
27.8
Sorting and related operations
[alg.sorting]
27.8.8
Heap operations
[alg.heap.operations]
27.8.8.1
General
[alg.heap.operations.general]
1
#
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
[
⌊
i
−
1
2
⌋
]
)
, 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
(
log
N
)
time
.
2
#
These properties make heaps useful as priority queues
.
3
#
make_
heap
converts a range into a heap and
sort_
heap
turns a heap into a sorted sequence
.