Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library Reference Guide

sort_heap()

Library:  Algorithms


Function

Local Index

No Entries

Summary

An algorithm that converts a heap into a sorted collection

Synopsis

#include <algorithm>

namespace std {
  template <class RandomAccessIterator>
  void
  sort_heap(RandomAccessIterator start,
            RandomAccessIterator finish);

  template <class RandomAccessIterator, class Compare>
  void
  sort_heap(RandomAccessIterator start,
            RandomAccessIterator finish, 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:

These properties make heaps useful as priority queues.

The sort_heap() algorithm converts a heap into a sorted collection over the range [start, finish) using either operator<() or the function object comp. Note that sort_heap() is not stable; equivalent elements are not guaranteed to remain in the same relative order after sort_heap() is applied.

Complexity

sort_heap() performs approximately N * log(N) comparisons, where N is equal to finish - start.

Example

See Also

make_heap(), pop_heap(), push_heap()

Standards Conformance

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.6.4



Previous fileTop of DocumentContentsIndex pageNext file