Man Page push_heap.3

                       Standard C++ Library
             Copyright 1998, 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 pro-
     perties 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 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  speci-
     fied.

     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. Then it
     properly positions 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 per-
     formed.

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 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, you always need to supply the Allocator template argu-
     ment. 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, sort_heap