Rogue Wave banner
Previous fileTop of documentContentsIndexNext file

sort_heap


Algorithm

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

Program Output

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



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