push_heap(3C++) - push_heap(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEpush_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 alter‐
nate 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 Output4 2 3 14 3 2 13 2 1 43 1 2 44 3 1 24 3 2 11 2 3 41 2 3 4WARNINGS
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 02 Apr 1998 push_heap(3C++)
