Predicate Versions of heap

Illustrates how to use the predicate versions of the heap STL function in Visual C++.

template<class RandomAccessIterator, class Compare> inline
   void make_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void sort_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void push_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void pop_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )

Remarks

Notes

The class/parameter names in the prototype do not match the version in the header file. Some have been modified to improve readability.

A heap is a sequence of elements organized like a binary tree. Each heap element corresponds to a tree node. The first value in the sequence [First..Last) is the root and is ordered by the predicate. For example, if the predicate is greater, every element in the heap satisfies the following statement: Every element is greater than or equal to its parent. The smallest element is stored in the root, and all children hold progressively larger values. The make_heap function converts the range [First..Last) into a heap. The sort_heap function sorts a sequence that was created using the make_heap function. The push_heap function inserts a new value into the heap. The pop_heap function swaps the first and last elements in the heap specified by [First, Last), and then reduces the length of the sequence by one before restoring the heap property. The predicate versions of the heap functions use the compare function for comparisons.

Example

// heap_PVfunctions.cpp
// compile with: /EHsc
// Illustrates how to use the predicate versions
// of the make_heap, sort_heap, push_heap
// and pop_heap functions.
//
// Functions:
//
//    make_heap : Convert a sequence to a heap.
//    sort_heap : Sort a heap.
//    push_heap : Insert an element in a heap.
//    pop_heap  : Remove the top element from a heap.
//////////////////////////////////////////////////////////////////////

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;


int main()
{
   const int VECTOR_SIZE = 8 ;

   // Define a template class vector of int
   typedef vector<int > IntVector ;

   //Define an iterator for template class vector of strings
   typedef IntVector::iterator IntVectorIt ;

   IntVector Numbers(VECTOR_SIZE) ;
   IntVectorIt it ;

   // Initialize vector Numbers
   Numbers[0] = 4 ;
   Numbers[1] = 10;
   Numbers[2] = 70 ;
   Numbers[3] = 10 ;
   Numbers[4] = 30 ;
   Numbers[5] = 69 ;
   Numbers[6] = 96 ;
   Numbers[7] = 100;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // convert Numbers into a heap
   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling make_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // sort the heapified sequence Numbers
   sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling sort_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   //insert an element in the heap
   Numbers.push_back(7) ;
   push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling push_heap()\n" << endl;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   //remove the root element from the heap Numbers
   pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling pop_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;
}

Numbers { 4 10 70 10 30 69 96 100  }

After calling make_heap

Numbers { 4 10 69 10 30 70 96 100  }

After calling sort_heap

Numbers { 100 96 70 69 30 10 10 4  }

After calling push_heap()

Numbers { 4 7 10 30 100 10 70 96 69  }

After calling pop_heap

Numbers { 7 30 10 69 100 10 70 96 4  }

Requirements

Header: <algorithm>

See Also

Concepts

Standard Template Library Samples