Was this page helpful?
Your feedback about this content is important. Let us know what you think.
Additional feedback?
1500 characters remaining
Export (0) Print
Expand All
abs
Expand Minimize
Important This document may not represent best practices for current development, links to downloads and other resources may no longer be valid. Current recommended version can be found here.

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
   )

NoteNote

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.

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

Output

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  }

Header: <algorithm>

Community Additions

ADD
Show:
© 2015 Microsoft