Loading...
Searching...
No Matches
MinHeap.hh
//FJSTARTHEADER
// $Id$
//
// Copyright (c) 2005-2021, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
//
//----------------------------------------------------------------------
// This file is part of FastJet.
//
// FastJet is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// The algorithms that underlie FastJet have required considerable
// development. They are described in the original FastJet paper,
// hep-ph/0512210 and in the manual, arXiv:1111.6097. If you use
// FastJet as part of work towards a scientific publication, please
// quote the version you use and include a citation to the manual and
// optionally also to hep-ph/0512210.
//
// FastJet is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with FastJet. If not, see <http://www.gnu.org/licenses/>.
//----------------------------------------------------------------------
//FJENDHEADER
#ifndef __FASTJET_MINHEAP__HH__
#define __FASTJET_MINHEAP__HH__
#include<vector>
#include<cassert>
#include<memory>
#include<limits>
#include "fastjet/internal/base.hh"
FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
//======================================================================
/// \if internal_doc
/// @ingroup internal
/// \class MinHeap
/// A class which provides a "heap"-like structure that allows
/// access to a the minimal value of a dynamically changing set of numbers
/// \endif
class MinHeap {
public:
/// construct a MinHeap from the vector of values, allowing future
/// expansion to a maximum size max_size;
MinHeap (const std::vector<double> & values, unsigned int max_size) :
_heap(max_size) {initialise(values);}
/// do the minimal setup for a MinHeap that can reach max_size;
/// initialisation must be performed later with the actual values.
MinHeap (unsigned int max_size) : _heap(max_size) {}
/// constructor in which the the maximum size is the size of the values array
MinHeap (const std::vector<double> & values) :
_heap(values.size()) {initialise(values);}
/// initialise the heap with the supplied values. Should only be called if
/// the constructor did not supply values.
void initialise(const std::vector<double> & values);
/// return the location of the minimal value on the heap
inline unsigned int minloc() const {
return (_heap[0].minloc) - &(_heap[0]);}
/// return the minimal value on the heap
inline double minval() const {return _heap[0].minloc->value;}
inline double operator[](int i) const {return _heap[i].value;}
/// remove the value at the specified location (i.e. replace it with
/// the largest possible value).
void remove(unsigned int loc) {
update(loc,std::numeric_limits<double>::max());};
/// update the value at the specified location
void update(unsigned int, double);
private:
struct ValueLoc{
double value;
ValueLoc * minloc;
};
std::vector<ValueLoc> _heap;
};
FASTJET_END_NAMESPACE
#endif // __FASTJET_MINHEAP__HH__
fastjet::MinHeap::MinHeap
MinHeap(const std::vector< double > &values)
constructor in which the the maximum size is the size of the values array
Definition MinHeap.hh:61
fastjet::MinHeap::MinHeap
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;
Definition MinHeap.hh:53
fastjet::MinHeap::update
void update(unsigned int, double)
update the value at the specified location
Definition MinHeap.cc:79
fastjet::MinHeap::MinHeap
MinHeap(unsigned int max_size)
do the minimal setup for a MinHeap that can reach max_size; initialisation must be performed later wi...
Definition MinHeap.hh:58
fastjet::MinHeap::remove
void remove(unsigned int loc)
remove the value at the specified location (i.e.
Definition MinHeap.hh:79
fastjet::MinHeap::minloc
unsigned int minloc() const
return the location of the minimal value on the heap
Definition MinHeap.hh:69
fastjet::MinHeap::minval
double minval() const
return the minimal value on the heap
Definition MinHeap.hh:73
fastjet::MinHeap::initialise
void initialise(const std::vector< double > &values)
initialise the heap with the supplied values.
Definition MinHeap.cc:47