push_heap()

Module:  Standard C++ Library   Library:  Algorithms

Function

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

An algorithm that places a new element into a heap

#include <algorithm>

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

  template <class RandomAccessIterator, class Compare>
  void
  push_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:

1. *a is the largest element in the range.

2. *a may be removed by the pop_heap() algorithm, or a new element may be added by the push_heap() algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The first overload of the push_heap() algorithm uses operator<() for comparison. The second overload uses the supplied binary predicate comp.

The push_heap() algorithm is used to add a new element to the heap. First, a new element for the heap is added to the end of a range. The push_heap() algorithm assumes that the range [start, finish - 1) is a valid heap. Then it properly positions the element in the location finish - 1 into its proper position in the heap, resulting in a heap over the range [start, finish).

For push_heap() at most log(finish - start) comparisons are performed.

//
//  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(), sort_heap()

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

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).