Search code examples
c++algorithmheap

Definition of heap used by std::is_heap and std::make_heap


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 comparator comp if bool(comp(first[(i - 1) / 2], first[i])) is false for all integer i in (​0​, last - first).

Since C++20 :

A random access range [first, last) is a heap with respect to a comparator comp if the range is a heap with respect to comp and std::identity{} (the identity projection).

Do you have a simpler definition? For example, when comp is std::less ? I don't understand the usage.


Solution

  • I finally found the answer on wikipedia, a heap is :

    • a tree stocked in an array,
    • where the parent of element i is at index (i-1)/2
    • every parent is greater than or equal to its child for a max heap (resp. lower for a min heap).