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

 NAME

   push_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
      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 alternate 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.  It	then properly posi-
   tions	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.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, 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, sort_heap

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