Node:Heap operations, Next:, Previous:Set operations on sorted structures, Up:Sorting and related operations


Heap operations

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are: (1) *a is the largest element in the range and (2) *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.

push_heap (RandomAccessIterator first, RandomAccessIterator last) Function
push_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

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

push_heap assumes the range [first, last - 1) is a valid heap and properly places the value in the location last - 1 into the resulting heap [first, last). At most \log(last - first) comparisons are performed.

pop_heap (RandomAccessIterator first, RandomAccessIterator last) Function
pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

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

pop_heap assumes the range [first, last) is a valid heap, then swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap. At most 2 * \log(last - first) comparisons are performed.

make_heap (RandomAccessIterator first, RandomAccessIterator last) Function
make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

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

make_heap constructs a heap out of the range [first, last). At most 3*(last - first) comparisons are performed.

sort_heap (RandomAccessIterator first, RandomAccessIterator last) Function
sort_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

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

sort_heap sorts elements in the heap [first, last). At most N \log N comparisons are performed where N is equal to last - first. sort_heap is not stable.