# 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> >

vector<int>

If your compiler does not support namespaces,  then  you  do
not need the using declaration for std.

```

```     pop_heap, push_heap and sort_heap

```