29 #include "fastjet/internal/MinHeap.hh" 34 FASTJET_BEGIN_NAMESPACE
45 void MinHeap::_initialise(
const std::vector<double> & values){
49 for (
unsigned i = values.size(); i < _heap.size(); i++) {
50 _heap[i].value = std::numeric_limits<double>::max();
51 _heap[i].minloc = &(_heap[i]);
56 for (
unsigned i = 0; i < values.size(); i++) {
57 _heap[i].value = values[i];
58 _heap[i].minloc = &(_heap[i]);
62 for (
unsigned i = _heap.size()-1; i > 0; i--) {
63 ValueLoc * parent = &(_heap[(i-1)/2]);
64 ValueLoc * here = &(_heap[i]);
65 if (here->minloc->value < parent->minloc->value) {
66 parent->minloc = here->minloc;
77 void MinHeap::update(
unsigned int loc,
double new_value) {
80 assert(loc < _heap.size());
81 ValueLoc * start = &(_heap[loc]);
85 if (start->minloc != start && !(new_value < start->minloc->value)) {
86 start->value = new_value;
92 start->value = new_value;
93 start->minloc = start;
95 bool change_made =
true;
97 ValueLoc * heap_end = (&(_heap[0])) + _heap.size();
101 ValueLoc * here = &(_heap[loc]);
105 if (here->minloc == start) {
106 here->minloc = here; change_made =
true;
110 ValueLoc * child = &(_heap[2*loc+1]);
111 if (child < heap_end && child->minloc->value < here->minloc->value ) {
112 here->minloc = child->minloc;
115 if (child < heap_end && child->minloc->value < here->minloc->value ) {
116 here->minloc = child->minloc;
120 if (loc == 0) {
break;}
126 FASTJET_END_NAMESPACE