// test_heap.cpp           STL algorithm running on a vector

#include <iostream>
#include <algorithm>
#include <functional>  // needed for   greater<int>()
#include <vector>
using namespace std;

// for printing contents of Numbers
#define put()  cout << "Numbers { "; for(it=Numbers.begin(); it!=Numbers.end(); it++) cout << *it << " " ; cout << " }" << endl << endl;

int main()
{
   const int VECTOR_SIZE = 8 ; // but vector will change size

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

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

   // Dedine the vector object and an iterator for the object
   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;

   cout << "test_heap running. Initial vector of eight integers." << endl;
   put();
   
   // convert Numbers into a heap
   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling make_heap()" << endl ;
   put();
   
   // sort the heapified sequence Numbers
   sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling sort_heap()" << endl ;
   put();

   // have to make the heap again
   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling make_heap() again" << endl ;
   put();

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

   //insert an element in the heap
   Numbers.push_back(92) ;
   push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling push_back(92) and push_heap()" << endl;
   put();

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

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

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

   //remove the root element from the heap Numbers
   pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   Numbers.pop_back();
   cout << "After calling pop_heap() pop_back()" << endl ;
   put();
   
   return 0;
}

// output from executing program:
// test_heap running. Initial vector of eight integers.
// 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 make_heap() again
// Numbers { 4 30 10 69 100 10 70 96  }
//
// After calling push_back(7) and push_heap()
// Numbers { 4 7 10 30 100 10 70 96 69  }
//
// After calling push_back(92) and push_heap()
// Numbers { 4 7 10 30 92 10 70 96 69 100  }
//
// After calling pop_heap() pop_bach()
// Numbers { 7 30 10 69 92 10 70 96 100  }
//
// After calling pop_heap() pop_back()
// Numbers { 10 30 10 69 92 100 70 96  }
//
// After calling pop_heap() pop_back()
// Numbers { 10 30 70 69 92 100 96  }
//
// After calling pop_heap() pop_back()
// Numbers { 30 69 70 96 92 100  }