|
fastjet 2.4.3
|
A class which provides a "heap"-like structure that allows access to a the minimal value of a dynamically changing set of numbers. More...
#include <MinHeap.hh>
Classes | |
| struct | ValueLoc |
Public Member Functions | |
| MinHeap (const std::vector< double > &values, unsigned int max_size) | |
| construct a MinHeap from the vector of values, allowing future expansion to a maximum size max_size; | |
| MinHeap (const std::vector< double > &values) | |
| constructor in which the the maximum size is the size of the values array | |
| unsigned int | minloc () const |
| return the location of the minimal value on the heap | |
| double | minval () const |
| return the minimal value on the heap | |
| double | operator[] (int i) const |
| void | remove (unsigned int loc) |
| remove the value at the specified location (i.e. | |
| void | update (unsigned int, double) |
| update the value at the specified location | |
Private Member Functions | |
| void | _initialise (const std::vector< double > &values) |
| construct the MinHeap; structure will be as follows: | |
Private Attributes | |
| std::vector< ValueLoc > | _heap |
A class which provides a "heap"-like structure that allows access to a the minimal value of a dynamically changing set of numbers.
Definition at line 45 of file MinHeap.hh.
| MinHeap::MinHeap | ( | const std::vector< double > & | values, |
| unsigned int | max_size | ||
| ) | [inline] |
construct a MinHeap from the vector of values, allowing future expansion to a maximum size max_size;
Definition at line 49 of file MinHeap.hh.
References _initialise().
:
_heap(max_size) {_initialise(values);};
| MinHeap::MinHeap | ( | const std::vector< double > & | values | ) | [inline] |
constructor in which the the maximum size is the size of the values array
Definition at line 53 of file MinHeap.hh.
References _initialise().
:
_heap(values.size()) {_initialise(values);};
| void MinHeap::_initialise | ( | const std::vector< double > & | values | ) | [private] |
construct the MinHeap; structure will be as follows:
_heap[0].minloc points to globally smallest entry _heap[1].minloc points to smallest entry in one half of heap _heap[2].minloc points to smallest entry in other half of heap
. for _heap[i], the "parent" is to be found at (i-1)/2
Definition at line 47 of file MinHeap.cc.
References MinHeap::ValueLoc::minloc, and MinHeap::ValueLoc::value.
Referenced by MinHeap().
{
// fill the high-range of the heap with the largest possible value
// (minloc of each entry is itself)
for (unsigned i = values.size(); i < _heap.size(); i++) {
_heap[i].value = std::numeric_limits<double>::max();
_heap[i].minloc = &(_heap[i]);
}
// fill the rest of the heap with the actual values
// (minloc of each entry is itself)
for (unsigned i = 0; i < values.size(); i++) {
_heap[i].value = values[i];
_heap[i].minloc = &(_heap[i]);
}
// now adjust the minlocs so that everything is OK...
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;
}
}
//cout << minloc() << " "<<sqrt(minval())<<endl;
//cout << sqrt(_heap[47].value)<<endl;
//cout << sqrt(_heap[48].value)<<endl;
//cout << sqrt(_heap[25].value)<<endl;
}
| unsigned int MinHeap::minloc | ( | ) | const [inline] |
return the location of the minimal value on the heap
Definition at line 57 of file MinHeap.hh.
References _heap.
Referenced by ClusterSequence::_minheap_faster_tiled_N2_cluster().
| double MinHeap::minval | ( | ) | const [inline] |
return the minimal value on the heap
Definition at line 61 of file MinHeap.hh.
References _heap.
Referenced by ClusterSequence::_minheap_faster_tiled_N2_cluster().
{return _heap[0].minloc->value;};
| double MinHeap::operator[] | ( | int | i | ) | const [inline] |
| void MinHeap::remove | ( | unsigned int | loc | ) | [inline] |
remove the value at the specified location (i.e.
replace it with the largest possible value).
Definition at line 67 of file MinHeap.hh.
References update().
Referenced by ClusterSequence::_minheap_faster_tiled_N2_cluster().
{
update(loc,std::numeric_limits<double>::max());};
| void MinHeap::update | ( | unsigned int | loc, |
| double | new_value | ||
| ) |
update the value at the specified location
Definition at line 79 of file MinHeap.cc.
References MinHeap::ValueLoc::minloc, and MinHeap::ValueLoc::value.
Referenced by ClusterSequence::_minheap_faster_tiled_N2_cluster(), and remove().
{
assert(loc < _heap.size());
ValueLoc * start = &(_heap[loc]);
// if the minloc is somewhere below us and our value is no smaller
// than the previous value, we can't possibly change the minloc
if (start->minloc != start && !(new_value < start->minloc->value)) {
start->value = new_value;
//std::cout << " had easy exit\n";
return;
}
// update the value and put a temporary location
start->value = new_value;
start->minloc = start;
// warn that a change has been made at this place
bool change_made = true;
// to make sure we don't go off edge...
ValueLoc * heap_end = (&(_heap[0])) + _heap.size();
// now work our way up the heap
while(change_made) {
ValueLoc * here = &(_heap[loc]);
change_made = false;
// if we were pointing to start, then we must re-initialise things
if (here->minloc == start) {
here->minloc = here; change_made = true;
}
// now compare current location to children (at 2*loc+1, 2*loc+2)
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;}
// then we move up (loc ->(loc-1)/2) if there's anywhere to go
if (loc == 0) {break;}
loc = (loc-1)/2;
}
}
std::vector<ValueLoc> MinHeap::_heap [private] |
Definition at line 80 of file MinHeap.hh.
Referenced by minloc(), minval(), and operator[]().
1.7.3