
Algorithm
Converts a heap into a sorted collection.
None
#include <algorithm> template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
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.
*a may be removed by pop_heap() or a new element may be added by push_heap(), in O(logN) time.
These properties make heaps useful as priority queues.
The sort_heap algorithm converts a heap into a sorted collection over the range [first, last) using either the default operator (<) or the comparison function supplied with the algorithm. Note that sort_heap is not stable (in other words, the elements may not be in the same relative order after sort_heap is applied).
sort_heap performs at most NlogN comparisons, where N is equal to last - first.
//
// 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+0,d1 + 4), v2(d2+0,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
If your compiler does not support default template parameters, then 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.
make_heap, pop_heap, push_heap