Standard C++	Library
 		 Copyright 1996, 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 properties are:

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

   2. *a	may be removed by pop_heap(), or a new element 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, i.e.,	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.h>

   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;
    }

   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

 WARNING

   If your compiler does	not support default template parameters, then
   you need to always supply	the Allocator template argument. For
   instance, you will need to write :

   vector<int, allocator<int> >

   instead of :

   vector<int>

 SEE ALSO

   make_heap, pop_heap, push_heap

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee