Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  pop_heap  - Moves the largest element off the heap.

SYNOPSIS

  template <class RandomAccessIterator>
   void
    pop_heap(RandomAccessIterator first,
            RandomAccessIterator last);

  template <class RandomAccessIterator, class Compare>
   void
    pop_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 pop_heap algorithm uses the less than (<) operator as the default
  comparison.  An alternate comparison operator can be specified.

  The pop_heap algorithm can be used as part of an operation to remove the
  largest element from a heap.  It assumes that the range [first, last) is a
  valid heap (i.e., that first is the largest element in the heap or the
  first element based on the alternate comparison operator).  It then swaps
  the value in the location first with the value in the location last - 1 and
  makes [first, last  -1)back into a heap.  You can then access the element
  in last using the vector or deque back() member function, or remove the
  element using the pop_back member function. Note that pop_heap does not
  actually remove the element from the data structure, you must use another
  function to do that.

COMPLEXITY

  pop_heap performs at most 2 * log(last - first) comparisons.

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 need to
  write :

  vector<int, allocator<int> >

  instead of :

  vector<int>

SEE ALSO

  make_heap, push_heap, sort_heap

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement