Man Page make_heap.3

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

NAME

     make_heap

      - Creates a heap.

SYNOPSIS

     #include <algorithm>
     template <class RandomAccessIterator>
      void
       make_heap(RandomAccessIterator first,
                RandomAccessIterator last);

     template <class RandomAccessIterator, class Compare>
      void
       make_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  can  be  added  by the push_heap algorithm, in
          O(logN) time.


     These properties make heaps useful as priority queues.

     The heap algorithms use less than (operator<) as the default
     comparison.  In  all  of  the  algorithms, an alternate com-
     parison operator can be specified.

     The first version of the make_heap  algorithm  arranges  the
     elements  in  the range [first, last) into a heap using less
     than (operator<) to perform comparisons. The second  version
     uses  the  comparison operator comp to perform the comparis-
     ons. Since the only requirements for  a  heap  are  the  two
     listed  above,  make_heap  is  not  required  to do anything
     within the range (first, last - 1).

COMPLEXITY

     This algorithm makes at most 3 * (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,  then you always need to supply the Allocator template
     argument. For instance, you have 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

     pop_heap, push_heap and sort_heap