fig20_37.cpp

经典vc教程的例子程序

// Fig. 20.37: fig20_37.cpp
// Demonstrating push_heap, pop_heap, make_heap and sort_heap.
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
   const int SIZE = 10;
   int a[ SIZE ] = { 3, 100, 52, 77, 22, 31, 1, 98, 13, 40 };
   int i;
   vector< int > v( a, a + SIZE ), v2;
   ostream_iterator< int > output( cout, " " );

   cout << "Vector v before make_heap:\n";
   copy( v.begin(), v.end(), output );
   make_heap( v.begin(), v.end() );
   cout << "\nVector v after make_heap:\n";
   copy( v.begin(), v.end(), output );
   sort_heap( v.begin(), v.end() );
   cout << "\nVector v after sort_heap:\n";
   copy( v.begin(), v.end(), output );

   // perform the heapsort with push_heap and pop_heap
   cout << "\n\nArray a contains: ";
   copy( a, a + SIZE, output );

   for ( i = 0; i < SIZE; ++i ) {
      v2.push_back( a[ i ] );
      push_heap( v2.begin(), v2.end() );      
      cout << "\nv2 after push_heap(a[" << i << "]): ";
      copy( v2.begin(), v2.end(), output );
   }
   
   for ( i = 0; i < v2.size(); ++i ) {
      cout << "\nv2 after " << v2[ 0 ] << " popped from heap\n";
      pop_heap( v2.begin(), v2.end() - i );
      copy( v2.begin(), v2.end(), output );
   }

   cout << endl;
   return 0;
}