2 // $Id: MinHeap.hh 293 2006-08-17 19:38:38Z salam $
4 // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam
6 //----------------------------------------------------------------------
7 // This file is part of FastJet.
9 // FastJet is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU General Public License as published by
11 // the Free Software Foundation; either version 2 of the License, or
12 // (at your option) any later version.
14 // The algorithms that underlie FastJet have required considerable
15 // development and are described in hep-ph/0512210. If you use
16 // FastJet as part of work towards a scientific publication, please
17 // include a citation to the FastJet paper.
19 // FastJet is distributed in the hope that it will be useful,
20 // but WITHOUT ANY WARRANTY; without even the implied warranty of
21 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 // GNU General Public License for more details.
24 // You should have received a copy of the GNU General Public License
25 // along with FastJet; if not, write to the Free Software
27 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 //----------------------------------------------------------------------
31 #ifndef __FASTJET_MINHEAP__HH__
32 #define __FASTJET_MINHEAP__HH__
38 #include "fastjet/internal/base.hh"
40 namespace fastjet { // defined in fastjet/internal/base.hh
42 //======================================================================
43 /// A class which provides a "heap"-like structure that allows
44 /// access to a the minimal value of a dynamically changing set of numbers
47 /// construct a MinHeap from the vector of values, allowing future
48 /// expansion to a maximum size max_size;
49 MinHeap (const std::vector<double> & values, unsigned int max_size) :
50 _heap(max_size) {_initialise(values);};
52 /// constructor in which the the maximum size is the size of the values array
53 MinHeap (const std::vector<double> & values) :
54 _heap(values.size()) {_initialise(values);};
56 /// return the location of the minimal value on the heap
57 inline unsigned int minloc() const {
58 return (_heap[0].minloc) - &(_heap[0]);};
60 /// return the minimal value on the heap
61 inline double minval() const {return _heap[0].minloc->value;};
63 inline double operator[](int i) const {return _heap[i].value;};
65 /// remove the value at the specified location (i.e. replace it with
66 /// the largest possible value).
67 void remove(unsigned int loc) {
68 update(loc,std::numeric_limits<double>::max());};
70 /// update the value at the specified location
71 void update(unsigned int, double);
80 std::vector<ValueLoc> _heap;
82 void _initialise(const std::vector<double> & values);
88 } // fastjet namespace
90 #endif // __FASTJET_MINHEAP__HH__