28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.7 Heap operations [alg.heap.operations]

1
#

A heap - это особая организация элементов в диапазоне между двумя итераторами произвольного доступа, [a, b) такая что:

  • (1.1)

    СN = b - a, для всехi,0<i<N, comp(a[⌊i−12⌋], a[i]) естьfalse.

  • (1.2)

    *a может быть удалено pop_­heap(), или новый элемент добавляет push_­heap()в O(logN) время.

2
#

Эти свойства делают кучи полезными в качестве очередей с приоритетом.

3
#

make_­heap() преобразует диапазон в кучу и sort_­heap() превращает кучу в отсортированную последовательность.

28.7.7.1 push_­heap [push.heap]

template<class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1
#

Requires: Диапазон [first, last - 1) должен быть допустимой кучей. Тип*first должен удовлетворятьMoveConstructible requirements и MoveAssignable requirements.

2
#

Effects: Помещает значение в указанное место last - 1 в полученную кучу [first, last).

3
#

Complexity: Максимум log(last - first) сравнений.

28.7.7.2 pop_­heap [pop.heap]

template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1
#

Requires: Диапазон [first, last) должен быть действительной непустой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип*first должен удовлетворять требованиям MoveConstructible и MoveAssignable.

2
#

Effects: Меняет местами значение в местоположенииfirst со значением в местоположении last - 1 и превращается [first, last - 1) в кучу.

3
#

Complexity: Максимум 2log(last - first) сравнений.

28.7.7.3 make_­heap [make.heap]

template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1
#

Requires: Тип*first должен удовлетворятьMoveConstructible requirements и MoveAssignable requirements.

2
#

Effects: Создает кучу вне диапазона [first, last).

3
#

Complexity: Максимум 3(last - first) сравнений.

28.7.7.4 sort_­heap [sort.heap]

template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1
#

Requires: Диапазон[first, last) должен быть допустимой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип*first должен удовлетворять требованиям MoveConstructible и MoveAssignable.

2
#

Effects: Сортирует элементы в куче [first, last).

3
#

Complexity: МаксимумNlogN сравнений, где N=last - first.

28.7.7.5 is_­heap [is.heap]

template<class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

1
#

Returns:is_­heap_­until(first, last) == last

template<class ExecutionPolicy, class RandomAccessIterator> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last);

2
#

Returns:is_­heap_­until(std​::​forward<ExecutionPolicy>(exec), first, last) == last

template<class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

3
#

Returns:is_­heap_­until(first, last, comp) == last

template<class ExecutionPolicy, class RandomAccessIterator, class Compare> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp);

4
#

Returns: 

is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last

template<class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp);

5
#

Returns: Если(last - first) < 2, вернется last. В противном случае, возвращает последний итераторi в[first, last] течение которого диапазон[first, i) является пирамидой.

6
#

Complexity: Линейный.