pop_heap(3C++) - pop_heap(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEpop_heap
- Moves the largest element off the heap.
SYNOPSIStemplate <;class RandomAccessIterator>
void
pop_heap(RandomAccessIterator first,
RandomAccessIterator last);
template <;class RandomAccessIterator, class Compare>
void
pop_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 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 (in other words, that first is the largest ele‐
ment 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 the range [first, last -1)back into
a heap. You can then access the element in last using the vector or
deque back() member function, or you can 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.
COMPLEXITYpop_heap performs at most 2 * log(last - first) comparisons.
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, push_heap, sort_heap
Rogue Wave Software 02 Apr 1998 pop_heap(3C++)
