Heap Ltd.
by Evgeniy Gabrilovich and Alex Gontmakher


Listing One

using namespace std;
template<class _Key,class _T> class KMaxValues:public vector<pair<_Key,_T> > {
   typedef vector<pair<_Key, _T> > Base;
   int _n; /* maximum size allowed */
   /* Block access to extraneous functions inherited from std::vector,
      lest their invocation might invalidate heap properties. */
   using Base::assign; using Base::erase; using Base::insert;
   using Base::pop_back; using Base::resize; using Base::swap;
   using Base::operator[];using Base::iterator;

   struct greater : public binary_function<value_type, value_type, bool> {
      bool operator()(const value_type& x, const value_type& y) const
         { return (x.first > y.first); }
    };
public:
   explicit KMaxValues(int maxSize = 1) : _n(maxSize) 
      { reserve(maxSize); /* preallocate storage */ }

   void push_back(const value_type& x) {
      if (size() < _n) {
         Base::push_back(x);
         push_heap(begin(), end(), greater());
      } else { /* maximum size reached */
         if (x.first < begin()->first)
            return; /* no need to add the element at all */
         /* delete the smallest element, then add the new one */
         pop_heap(begin(), end(), greater());
         (*this)[_n-1] = x; /* inserts the new element into last position */
         push_heap(begin(), end(), greater()); /* restore heap property */
      }
   }
};







1


