[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, 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 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 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  (in  other  words,
     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 the range [first, last   -1)back
     into  a  heap. You can then access the element in last using
     the vector or deque  back()  member  function,  or  you  can
     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>
     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, push_heap, sort_heap

Партнёры:

Хостинг: