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 added by the

push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The push_heap algorithms uses the less than (<) operator as the default comparison. As with all

of the heap manipulation algorithms, an alternate comparison function can be specified.

The push_heap algorithm is used to add a new element to the heap. First, a new element for the

heap is added to the end of a range. (For example, you can use the vector or deque member

function push_back()to add the element to the end of either of those containers.) The

push_heap algorithm assumes that the range [first, last - 1) is a valid heap. It then properly

positions the element in the location last - 1 into its proper position in the heap, resulting in a

heap over the range [first, last).

Note that the push_heap algorithm does not place an element into the heap's underlying

container. You must user another function to add the element to the end of the container before

applying push_heap.

Complexity

For push_heap at most log(last - first) comparisons are performed.

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>());