Was this page helpful?
Your feedback about this content is important. Let us know what you think.
Additional feedback?
1500 characters remaining
Export (0) Print
Expand All
max
min
Expand Minimize
Important This document may not represent best practices for current development, links to downloads and other resources may no longer be valid. Current recommended version can be found here.

sort_heap

Converts a heap into a sorted range.

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

_First

A random-access iterator addressing the position of the first element in the target heap.

_Last

A random-access iterator addressing the position one past the final element in the target heap.

_Comp

User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

Heaps have two properties:

  • The first element is always the largest.

  • Elements may be added or removed in logarithmic time.

After the application if this algorithm, the range it was applied to is no longer a heap.

This is not a stable sort because the relative order of equivalent elements is not necessarily preserved.

Heaps are an ideal way to implement priority queues and they are used in the implementation of the Standard Template Library container adaptor priority_queue Class.

The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

The complexity is at most N log N, where N = (_Last – _First).

// alg_sort_heap.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

int main( ) {
   using namespace std;
   vector <int> v1, v2;
   vector <int>::iterator Iter1, Iter2;

   int i;
   for ( i = 1 ; i <= 9 ; i++ )
      v1.push_back( i );

   random_shuffle( v1.begin( ), v1.end( ) );

   cout << "Vector v1 after random_shuffle is ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // Make v1 a heap
   make_heap(v1.begin(), v1.end());
   cout << "Vector v1 after first make_heap is ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // Sort heap v1 with default less-than ordering
   sort_heap (v1.begin( ), v1.end( ) );
   cout << "The heap v1 becomes the sorted range: ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // Make v1 a heap with greater than ordering
   make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
   cout << "The greater-than heaped version of v1 is\n ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   sort_heap(v1.begin( ), v1.end( ), greater<int>( ) );
   cout << "The greater-than heap v1 becomes the sorted range\n ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;
}

Vector v1 after random_shuffle is ( 9 2 7 3 1 6 8 4 5 ).
Vector v1 after first make_heap is ( 9 5 8 4 1 6 7 2 3 ).
The heap v1 becomes the sorted range: ( 1 2 3 4 5 6 7 8 9 ).
The greater-than heaped version of v1 is
( 1 2 3 4 5 6 7 8 9 ).
The greater-than heap v1 becomes the sorted range
( 9 8 7 6 5 4 3 2 1 ).

Header: <algorithm>

Namespace: std

Community Additions

ADD
Show:
© 2015 Microsoft