MinHeap

Collaboration diagram for MinHeap:

Classes
struct	ValueLoc

Public Member Functions
	MinHeap (const std::vector< double > &values, unsigned int max_size)
	MinHeap (unsigned int max_size)
	MinHeap (const std::vector< double > &values)
void	initialise (const std::vector< double > &values)
unsigned int	minloc () const
double	minval () const
double	operator[] (int i) const
void	remove (unsigned int loc)
void	update (unsigned int, double)

Private Attributes
std::vector< ValueLoc >	_heap

Constructor & Destructor Documentation

MinHeap() [1/3]

MinHeap ( const std::vector< double > &  values, unsigned int  max_size  )

inline

                                                                    :
    _heap(max_size) {initialise(values);}

MinHeap() [2/3]

MinHeap ( unsigned int  max_size )

inline

: _heap(max_size) {}

MinHeap() [3/3]

MinHeap ( const std::vector< double > &  values )

inline

                                             :
    _heap(values.size()) {initialise(values);}

Member Function Documentation

initialise()

void initialise

(

const std::vector< double > &

values

)

                                                        {
  for (unsigned i = values.size(); i < _heap.size(); i++) {
    _heap[i].value = std::numeric_limits<double>::max();
    _heap[i].minloc = &(_heap[i]);
  }
  for (unsigned i = 0; i < values.size(); i++) {
    _heap[i].value = values[i];
    _heap[i].minloc = &(_heap[i]);
  }
  for (unsigned i = _heap.size()-1; i > 0; i--) {
    ValueLoc * parent = &(_heap[(i-1)/2]);
    ValueLoc * here   = &(_heap[i]);
    if (here->minloc->value < parent->minloc->value) {
      parent->minloc = here->minloc;
    }
  }
}

minloc()

unsigned int minloc ( ) const

inline

                                     {
    return (_heap[0].minloc) - &(_heap[0]);}

minval()

double minval ( ) const

inline

{return _heap[0].minloc->value;}

operator[]()

double operator[] ( int  i ) const

inline

{return _heap[i].value;}

remove()

void remove ( unsigned int  loc )

inline

                                {
    update(loc,std::numeric_limits<double>::max());};

update()

void update	(	unsigned int	loc,
		double	new_value
	)

                                                       {
  assert(loc < _heap.size());
  ValueLoc * start = &(_heap[loc]);
  if (start->minloc != start && !(new_value < start->minloc->value)) {
    start->value = new_value;
    return;
  }
  start->value = new_value;
  start->minloc = start;
  bool change_made = true;
  ValueLoc * heap_end = (&(_heap[0])) + _heap.size();
  while(change_made) {
    ValueLoc * here = &(_heap[loc]);
    change_made     = false;
    if (here->minloc == start) {
      here->minloc = here; change_made = true;
    }
    ValueLoc * child = &(_heap[2*loc+1]);
    if (child < heap_end && child->minloc->value < here->minloc->value ) {
      here->minloc = child->minloc;
      change_made = true;}
    child++;
    if (child < heap_end && child->minloc->value < here->minloc->value ) {
      here->minloc = child->minloc;
      change_made = true;}
    if (loc == 0) {break;}
    loc = (loc-1)/2;
  }
}

Member Data Documentation

_heap

std::vector<ValueLoc> _heap

private

---

The documentation for this class was generated from the following file:

• /builds/cms-analysis/general/DasAnalysisSystem/Core/Installer/Core/JetObservables/src/fjcore.cc