push_heap

Algorithms

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

Places a new element into a heap.

None

#include <algorithm>
template <class RandomAccessIterator>
  void
  push_heap(RandomAccessIterator first,
            RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
  void
  push_heap(RandomAccessIterator first,
            RandomAccessIterator last, 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 push_heap algorithms uses the less than (<) operator as the default comparison. As with all of the heap manipulation algorithms, an alternate comparison function can be specified.

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. (For example, you can use the vector or deque member function push_back()to add the element to the end of either of those containers.) The push_heap algorithm assumes that the range [first, last - 1) is a valid heap. Then it properly positions the element in the location last - 1 into its proper position in the heap, resulting in a heap over the range [first, last).

Note that the push_heap algorithm does not place an element into the heap's underlying container. You must user another function to add the element to the end of the container before applying push_heap.

For push_heap at most log(last - first) comparisons are performed.

//
// 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 

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.

make_heap, pop_heap, sort_heap