## sort_heap

    Algorithm

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

### Summary

Converts a heap into a sorted collection.

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

None

### Synopsis

    #include <algorithm>
    template <class RandomAccessIterator>
    void
    sort_heap(RandomAccessIterator first,
    RandomAccessIterator last);
    template <class RandomAccessIterator, class Compare>
    void
    sort_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 `pop_heap()` or a new element may be added by `push_heap()`, in `O(logN)` time.

These properties make heaps useful as priority queues.

The sort_heap algorithm converts a heap into a sorted collection over the range `[first, last)` using either the default operator (`<`) or the comparison function supplied with the algorithm. Note that sort_heap is not stable (in other words, the elements may not be in the same relative order after sort_heap is applied).

### Complexity

sort_heap performs at most `NlogN` comparisons, where `N` is equal to `last - first`.

### 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+0,d1 + 4), v2(d2+0,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 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, pop_heap, push_heap

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