## make_heap

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Creates a heap.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### 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 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 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 comparison 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 comparisons. 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 parameters, 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

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998