Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

NAME

 
push_heap
 
 - Places a new element into a heap.
 
 
 

SYNOPSIS

#include <algorithm>
template <class RandomAccessIterator>

void

push_heap(RandomAccessIterator first,

RandomAccessIterator last);

 
template <class RandomAccessIterator, class Compare>

void

push_heap(RandomAccessIterator first,

RandomAccessIterator last, Compare comp);
 
 
 

DESCRIPTION

 
 
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. 

2.∗a may be removed by the pop_heap algorithm, or a new element may be 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. Then it 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>

using namespace std;
 
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.

// Copy both vectors to cout

ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;

// Now let’s pop

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

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

// Copy both vectors to cout

copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;

 
// And push
push_heap(v1.begin(),v1.end());

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

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

// Copy both vectors to cout

copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;

// Now sort those heaps

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

// v1 = v2 = (1,2,3,4)

// Copy both vectors to cout

copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;

return 0;

}
 

Program Output
 
 
 

 
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
 
 
 

WARNINGS

 
 
If your compiler does not support default template parameters, you always need to supply the Allocator template argument. For instance, you need to write:
 
vector<int, allocator<int> >
 
instead of:
 
vector<int>
 
If your compiler does not support namespaces, then you do not need the using declaration for std. 
 
 
 

SEE ALSO

 
 
make_heap, pop_heap, sort_heap
 

Rogue Wave Software  —  Last change: 02 Apr 1998