United States    
COMPAQ STORE | PRODUCTS | SERVICES | SUPPORT
| CONTACT US | SEARCH
C++
push_heap (3C++std) - Tru64 UNIX
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
  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 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
  

1.800.AT.COMPAQ

privacy and legal statement