Man Page sort_heap.3

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

NAME

     sort_heap

      - Converts a heap into a sorted collection.

SYNOPSIS

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

DESCRIPTION

     A heap is a particular organization of elements in  a  range
     between two random access iterators [a, b). Its two key pro-
     perties are:



     1.   *a is the largest element in the range.

     2.   *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  col-
     lection  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).

COMPLEXITY

     sort_heap performs at most NlogN  comparisons,  where  N  is
     equal to last - first.

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+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

WARNINGS

     If your compiler does not support default  template  parame-
     ters,  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.

SEE ALSO

     make_heap, pop_heap, push_heap