A heap is a particular organization of elements in a range between two random access iterators [a,b). Its two key properties are:
There is no element greater than *a in the range and
*a may be removed by pop_heap(), or a new element added by push_heap(), in O(log(N)) time.
These properties make heaps useful as priority queues.
make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.
25.4.6.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);
Effects: Places the value in the location last - 1 into the resulting heap [first,last).
Requires: The range [first,last - 1) shall be a valid heap. The type of *first shall satisfy the MoveConstructible requirements (Table [moveconstructible]) and the MoveAssignable requirements (Table [moveassignable]).
Complexity: At most log(last - first) comparisons.
25.4.6.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);
Requires: The range [first,last) shall be a valid non-empty heap. RandomAccessIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [moveconstructible]) and of MoveAssignable (Table [moveassignable]).
Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first,last - 1) into a heap.
Complexity: At most 2 * log(last - first) comparisons.
25.4.6.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);
Effects: Constructs a heap out of the range [first,last).
Complexity: At most 3 * (last - first) comparisons.
25.4.6.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);
Effects: Sorts elements in the heap [first,last).
Requires: The range [first,last) shall be a valid heap. RandomAccessIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [moveconstructible]) and of MoveAssignable (Table [moveassignable]).
Complexity: At most N log(N) comparisons (where N == last - first).
25.4.6.5 is_heap [is.heap] template<class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
Returns: is_heap_until(first, last) == last
template<class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Returns: is_heap_until(first, last, comp) == last
template<class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Returns: If distance(first, last) < 2, returns last. Otherwise, returns the last iterator i in [first,last] for which the range [first,i) is a heap.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4