C++ STL algorithm, make_heap(), push_heap(), sort_heap() and pop_heap() program example
Compiler: Visual C++ Express Edition 2005
Compiled on Platform: Windows XP Pro SP2
Header file: Standard
Additional project setting: Set project to be compiled as C++
Project -> your_project_name Properties -> Configuration Properties -> C/C++ -> Advanced -> Compiled As: Compiled as C++ Code (/TP)
Other info: none
To do: Using the C++ make_heap(), push_heap(), sort_heap() and pop_heap() in C++ programming
To show: How to use the C++ algorithm, make_heap(), push_heap(), sort_heap() and pop_heap() in C++ programming
// C++ STL algorithm, make_heap(), push_heap(), sort_heap(), pop_heap() example
// 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
//
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
int main(void)
{
// define a template class vector of int, simplified the name using typedef
typedef vector<int, allocator<int> > IntVector ;
// define an iterator for template class vector of strings, simplified the name using typedef
typedef IntVector::iterator IntVectorIt ;
IntVector IntNum(10) ;
IntVectorIt it ;
// initialize vector IntNum
IntNum[0] = 77 ;
IntNum[1] = 33;
IntNum[2] = 44 ;
IntNum[3] = 33 ;
IntNum[4] = 55 ;
IntNum[5] = 66 ;
IntNum[6] = 99 ;
IntNum[7] = 88;
IntNum[8] = 88;
IntNum[9] = 88;
// print content of IntNum
cout<<"IntNum vector is: ";
for(it = IntNum.begin(); it != IntNum.end(); it++)
cout<<*it<<" " ;
cout<<endl<<endl;
// convert IntNum vector into a heap
make_heap(IntNum.begin(), IntNum.end());
// print content of IntNum vector
cout<<"After calling make_heap(), IntNum vector is: ";
for(it = IntNum.begin(); it != IntNum.end(); it++)
cout<<*it<<" ";
cout<<endl;
// sort the heapified sequence IntNum vector
sort_heap(IntNum.begin(), IntNum.end()) ;
// print content of IntNum vector
cout<<"After calling sort_heap(), IntNum vector is: ";
for(it = IntNum.begin(); it != IntNum.end(); it++)
cout<<*it<<" ";
cout<<endl;
// you need to call make_heap() to re-assert the heap property
make_heap(IntNum.begin(), IntNum.end());
// insert an element in the heap
cout<<"Inserting element using push_back(8)..."<<endl;
IntNum.push_back(8);
push_heap(IntNum.begin(), IntNum.end());
// print content of IntNum
cout << "After calling make_heap() and push_heap(), IntNum vector is: ";
for(it = IntNum.begin(); it != IntNum.end(); it++)
cout<<*it<<" ";
cout<<endl;
// remove the root element from the heap IntNum vector
pop_heap(IntNum.begin(), IntNum.end());
// print content of IntNum
cout<<"After calling pop_heap(), IntNum vector is: ";
for(it = IntNum.begin(); it != IntNum.end(); it++)
cout<<*it<<" ";
cout<<endl<<endl ;
return 0;
}
Output examples:
IntNum vector is: 77 33 44 33 55 66 99 88 88 88
After calling make_heap(), IntNum vector is: 99 88 77 88 55 66 44 88 33 33
After calling sort_heap(), IntNum vector is: 33 33 44 55 66 77 88 88 88 99
Inserting element using push_back(8)...
After calling make_heap() and push_heap(), IntNum vector is: 99 88 88 88 66 77 44 33 55 33 8
After calling pop_heap(), IntNum vector is: 88 88 77 88 66 8 44 33 55 33 99
Press any key to continue . . .