Определение кучи, используемое std::is_heap и std::make_heap
Согласно этой странице, существует два определения heap (используется std::make_heap, std::is_heap и т. д.):
До С++20:
Диапазон произвольного доступа [
first,last) представляет собой кучу относительно компараторcomp, еслиbool(comp(first[(i - 1) / 2], first[i]))естьfalseдля всех целых чиселiв (0,last - first).
Начиная с С++20:
Диапазон произвольного доступа [
first,last) является кучей относительно компаратораcomp, если диапазон является кучей относительноcompиstd::identity{}(проекция личности).
У вас есть более простое определение? Например, когда comp — это std::less? Я не понимаю использования.
ОК, большое спасибо, я отредактирую вопрос, удалю примечание об ошибке и позволю запросить более четкое определение.
Ответы 1
Наконец-то я нашел ответ в Википедии, heap это:
treeхранится вarray,- где родительский элемент
iнаходится по индексу(i-1)/2 - каждый родитель больше или равен своему ребенку для
max heap(соответственно ниже дляmin heap).
«в
(0, last - first)» — это эксклюзивный диапазон: ни 0, ниlast - firstне являются его частями. Они заимствовали общепринятые математические обозначения — в одном предложении можно увидеть диапазон[first, last), в который входитfirst, но нетlast. Квадратные скобки означают «включая», скобки означают «исключая», и их можно сопоставлять в любой комбинации. Более подробное определение смотрите в Wiki.