According to this page, there a two definitions of a heap
(used by std::make_heap
, std::is_heap
, etc..) :
Until C++20 :
A random access range [
first
,last
) is a heap with respect to a comparatorcomp
ifbool(comp(first[(i - 1) / 2], first[i]))
isfalse
for all integeri
in (0
,last - first
).
Since C++20 :
A random access range [
first
,last
) is a heap with respect to a comparatorcomp
if the range is a heap with respect tocomp
andstd::identity{}
(the identity projection).
Do you have a simpler definition? For example, when comp
is std::less
? I don't understand the usage.
I finally found the answer on wikipedia, a heap
is :
tree
stocked in an array
,i
is at index (i-1)/2
max heap
(resp. lower for a min heap
).