## pop_heap

    Algorithms

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Moves the largest element off the heap.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    template <class RandomAccessIterator>
      void
      pop_heap(RandomAccessIterator first,
               RandomAccessIterator last);

    template <class RandomAccessIterator, class Compare>
      void
      pop_heap(RandomAccessIterator first,
               RandomAccessIterator last, 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:

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 pop_heap algorithm uses the less than (`<`) operator as the default comparison. An alternate comparison operator can be specified.

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 `[first, last)` is a valid heap (in other words, that `first` 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 `first` with the value in the location `last - 1` and makes the range `[first, last -1)`back into a heap. You can then access the element in `last` using the vector or deque `back()` member function, or you can remove the element using the `pop_back` member function. Note that pop_heap does not actually remove the element from the data structure; you must use another function to do that.

### Complexity

pop_heap performs at most `2 * log(last - first)` comparisons.

### Example

    //
    // heap_ops.cpp
    //
     #include <algorithm>
     #include <vector>
     #include <iostream>
     using namespace std;

     int main(void)
     {
       int d1[4] = {1,2,3,4};
       int d2[4] = {1,3,2,4};

       // Set up two vectors
       vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

       // Make heaps
       make_heap(v1.begin(),v1.end());
       make_heap(v2.begin(),v2.end(),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
       ostream_iterator<int,char> out(cout," ");
       copy(v1.begin(),v1.end(),out);
       cout << endl;
       copy(v2.begin(),v2.end(),out);
       cout << endl;

       // Now let's pop
       pop_heap(v1.begin(),v1.end());
       pop_heap(v2.begin(),v2.end(),less<int>());
       // v1 = (3,x,y,4) and v2 = (3,x,y,4)

       // Copy both vectors to cout
       copy(v1.begin(),v1.end(),out);
       cout << endl;
       copy(v2.begin(),v2.end(),out);
       cout << endl;

       // And push
       push_heap(v1.begin(),v1.end());
       push_heap(v2.begin(),v2.end(),less<int>());
       // v1 = (4,x,y,z) and v2 = (4,x,y,z)

       // Copy both vectors to cout
       copy(v1.begin(),v1.end(),out);
       cout << endl;
       copy(v2.begin(),v2.end(),out);
       cout << endl;

       // Now sort those heaps
       sort_heap(v1.begin(),v1.end());
       sort_heap(v2.begin(),v2.end(),less<int>());
       // v1 = v2 = (1,2,3,4)

       // Copy both vectors to cout
       copy(v1.begin(),v1.end(),out);
       cout << endl;
       copy(v2.begin(),v2.end(),out);
       cout << endl;

       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

### Warnings

If your compiler does not support default template parameters, you always need to supply the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator<int> >`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

make_heap, push_heap, sort_heap

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998