Standard C++ Library Class Reference

*a is the largest element in the range.1.

*a may be removed by the pop_heap algorithm or a new element added by the

push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The pop_heap algorithm uses the less than (<) operator as the default comparison. An alternate

comparison operator can be specified.

The pop_heap algorithm can be used as part of an operation to remove the largest element from

a heap. It assumes that the range [first, last) is a valid heap (i.e., that first is the largest element

in the heap or the first element based on the alternate comparison operator). It then swaps the

value in the location first with the value in the location last - 1 and makes [first, last -1)back into

a heap. You can then access the element in last using the vector or deque back() member

function, or remove the element using the pop_back member function. Note that pop_heap does

not actually remove the element from the data structure, you must use another function to do

that.

Complexity

pop_heap performs at most 2 * log(last - first) comparisons.

Example

// heap_ops.cpp

#include <algorithm>

#include <vector>

#include <iostream.h>

int main(void)

{

int d1[4] = {1,2,3,4};

int d2[4] = {1,3,2,4};

// Set up two vectors

vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

// Make heaps

make_heap(v1.begin(),v1.end());

make_heap(v2.begin(),v2.end(),less<int>());

// v1 = (4,x,y,z) and v2 = (4,x,y,z)

// Note that x, y and z represent the remaining

// values in the container (other than 4).

// The definition of the heap and heap operations

// does not require any particular ordering

// of these values.