00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #ifndef __FASTJET_MINHEAP__HH__
00032 #define __FASTJET_MINHEAP__HH__
00033
00034 #include<vector>
00035 #include<cassert>
00036 #include<memory>
00037 #include<limits>
00038 #include "fastjet/internal/base.hh"
00039
00040 FASTJET_BEGIN_NAMESPACE
00041
00042
00045 class MinHeap {
00046 public:
00049 MinHeap (const std::vector<double> & values, unsigned int max_size) :
00050 _heap(max_size) {_initialise(values);};
00051
00053 MinHeap (const std::vector<double> & values) :
00054 _heap(values.size()) {_initialise(values);};
00055
00057 inline unsigned int minloc() const {
00058 return (_heap[0].minloc) - &(_heap[0]);};
00059
00061 inline double minval() const {return _heap[0].minloc->value;};
00062
00063 inline double operator[](int i) const {return _heap[i].value;};
00064
00067 void remove(unsigned int loc) {
00068 update(loc,std::numeric_limits<double>::max());};
00069
00071 void update(unsigned int, double);
00072
00073 private:
00074
00075 struct ValueLoc{
00076 double value;
00077 ValueLoc * minloc;
00078 };
00079
00080 std::vector<ValueLoc> _heap;
00081
00082 void _initialise(const std::vector<double> & values);
00083
00084
00085 };
00086
00087
00088 FASTJET_END_NAMESPACE
00089
00090 #endif // __FASTJET_MINHEAP__HH__