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

 

 

C and C++ Programming Resources | C & C++ Code Example Index