1

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.

2
  • 3
    "in (0, last - first)" is an exclusive range - neither 0 nor last - first are parts of it. They borrowed common math notation - you can see [first, last) range in the same sentence, which includes first but not last. Square brackets mean "including", parens mean "excluding", and they can be matched in any combination. For a more detailed definition, see Wiki.
    – STerliakov
    Commented Aug 3 at 16:12
  • ok thanks a lot, i will edit the question to remove the note about the error and let a request for a clearer defintion. Commented Aug 3 at 16:13

1 Answer 1

2

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.