pop_heap()

Library:  Algorithms

Function

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

Algorithm that moves the largest element off the heap

#include <algorithm>

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

template <class RandomAccessIterator, class Compare>
  void
  pop_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 pop_heap() algorithm, in O(log(N)) time.

These properties make heaps useful as priority queues.

The pop_heap() algorithm uses operator<() as the default comparison. An alternate comparison operator can be specified to the second overload of the function template.

The pop_heap() algorithm can be used as part of an operation to remove the largest element from a heap. It assumes that the range [start, finish) is a valid heap (in other words, that start is the largest element in the heap or the first element based on the alternate comparison operator). It then swaps the value in the location start with the value in the location finish - 1 and makes the range [start, finish - 1) back into a heap.

pop_heap() performs at most 2 * log(finish - start) comparisons.

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

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