Standard C++ Library Class Reference

Description

A heap is a particular organization of elements in a range between two random access iterators

[a, b). Its two key properties are:

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

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

push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The heap algorithms use less than (operator<) as the default comparison. In all of the

algorithms, an alternate comparison operator can be specified.

The first version of the make_heap algorithm arranges the elements in the range [first, last) into

a heap using less than (operator<) to perform comparisons. The second version uses the

comparison operator comp to perform the comparisons. Since the only requirements for a heap

are the two listed above, make_heap is not required to do anything within the range (first, last -

1).

Complexity

This algorithm makes at most 3 * (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