sort_heap()

Module:  Standard C++ Library   Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

An algorithm that converts a heap into a sorted collection

#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);
}

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

• *a is the largest element in the range.

• *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 [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.

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

//
//  heap_ops.cpp
//

#include <algorithm>    // for copy, make_heap, pop_heap, 
                        // and push_heap
#include <functional>   // for less
#include <iostream>     // for cout
#include <iterator>     // for ostream_iterator
#include <vector>       // for vector



template <class charT, class Traits, class T, class Allocator>
void print_vector (std::basic_ostream<charT, Traits> &strm,
                   const std::vector<T, Allocator>   &v)
{
    std::copy (v.begin (), v.end (),
               std::ostream_iterator<T, charT, Traits> 
                                    (strm, " "));

    strm << std::endl;
}


int main ()
{
    typedef std::vector<int, std::allocator<int> > Vector;

    const Vector::value_type d1[] = { 1, 2, 3, 4 };
    const Vector::value_type d2[] = { 1, 3, 2, 4 };

    // Set up two vectors.
    Vector v1 (d1 + 0, d1 + sizeof d1 / sizeof *d1);
    Vector v2 (d2 + 0, d2 + sizeof d2 / sizeof *d2);

    // Make heaps.
    std::make_heap (v1.begin (), v1.end ());
    std::make_heap (v2.begin (), v2.end (), std::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.
    print_vector (std::cout, v1);
    print_vector (std::cout, v2);

    // Now let's pop.
    std::pop_heap (v1.begin (), v1.end ());
    std::pop_heap (v2.begin (), v2.end (), std::less<int>());

    print_vector (std::cout, v1);
    print_vector (std::cout, v2);

    // And push.
    std::push_heap (v1.begin (), v1.end ());
    std::push_heap (v2.begin (), v2.end (), std::less<int>());

    print_vector (std::cout, v1);
    print_vector (std::cout, v2);

    // Now sort those heaps.
    std::sort_heap (v1.begin (), v1.end ());
    std::sort_heap (v2.begin (), v2.end (), std::less<int>());

    print_vector (std::cout, v1);
    print_vector (std::cout, v2);

    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 

make_heap(), pop_heap(), push_heap()

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

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).