FST  openfst-1.7.1
OpenFst Library
heap.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Implementation of a heap as in STL, but allows tracking positions in heap
5 // using a key. The key can be used to do an in-place update of values in the
6 // heap.
7 
8 #ifndef FST_HEAP_H_
9 #define FST_HEAP_H_
10 
11 #include <utility>
12 #include <vector>
13 
14 #include <fst/compat.h>
15 namespace fst {
16 
17 // A templated heap implementation that supports in-place update of values.
18 //
19 // The templated heap implementation is a little different from the STL
20 // priority_queue and the *_heap operations in STL. This heap supports
21 // indexing of values in the heap via an associated key.
22 //
23 // Each value is internally associated with a key which is returned to the
24 // calling functions on heap insert. This key can be used to later update
25 // the specific value in the heap.
26 //
27 // T: the element type of the hash. It can be POD, Data or a pointer to Data.
28 // Compare: comparison functor for determining min-heapness.
29 template <class T, class Compare>
30 class Heap {
31  public:
32  using Value = T;
33 
34  static constexpr int kNoKey = -1;
35 
36  // Initializes with a specific comparator.
37  explicit Heap(Compare comp = Compare()) : comp_(comp), size_(0) {}
38 
39  // Inserts a value into the heap.
40  int Insert(const Value &value) {
41  if (size_ < values_.size()) {
42  values_[size_] = value;
43  pos_[key_[size_]] = size_;
44  } else {
45  values_.push_back(value);
46  pos_.push_back(size_);
47  key_.push_back(size_);
48  }
49  ++size_;
50  return Insert(value, size_ - 1);
51  }
52 
53  // Updates a value at position given by the key. The pos_ array is first
54  // indexed by the key. The position gives the position in the heap array.
55  // Once we have the position we can then use the standard heap operations
56  // to calculate the parent and child positions.
57  void Update(int key, const Value &value) {
58  const auto i = pos_[key];
59  const bool is_better = comp_(value, values_[Parent(i)]);
60  values_[i] = value;
61  if (is_better) {
62  Insert(value, i);
63  } else {
64  Heapify(i);
65  }
66  }
67 
68  // Returns the least value.
69  Value Pop() {
70  Value top = values_.front();
71  Swap(0, size_-1);
72  size_--;
73  Heapify(0);
74  return top;
75  }
76 
77  // Returns the least value w.r.t. the comparison function from the
78  // heap.
79  const Value &Top() const { return values_.front(); }
80 
81  // Returns the element for the given key.
82  const Value &Get(int key) const { return values_[pos_[key]]; }
83 
84  // Checks if the heap is empty.
85  bool Empty() const { return size_ == 0; }
86 
87  void Clear() { size_ = 0; }
88 
89  int Size() const { return size_; }
90 
91  void Reserve(int size) {
92  values_.reserve(size);
93  pos_.reserve(size);
94  key_.reserve(size);
95  }
96 
97  const Compare &GetCompare() const { return comp_; }
98 
99  private:
100  // The following private routines are used in a supportive role
101  // for managing the heap and keeping the heap properties.
102 
103  // Computes left child of parent.
104  static int Left(int i) {
105  return 2 * (i + 1) - 1; // 0 -> 1, 1 -> 3
106  }
107 
108  // Computes right child of parent.
109  static int Right(int i) {
110  return 2 * (i + 1); // 0 -> 2, 1 -> 4
111  }
112 
113  // Given a child computes parent.
114  static int Parent(int i) {
115  return (i - 1) / 2; // 0 -> 0, 1 -> 0, 2 -> 0, 3 -> 1, 4 -> 1, ...
116  }
117 
118  // Swaps a child and parent. Use to move element up/down tree. Note the use of
119  // a little trick here. When we swap we need to swap:
120  //
121  // - the value
122  // - the associated keys
123  // - the position of the value in the heap
124  void Swap(int j, int k) {
125  const auto tkey = key_[j];
126  pos_[key_[j] = key_[k]] = j;
127  pos_[key_[k] = tkey] = k;
128  using std::swap;
129  swap(values_[j], values_[k]);
130  }
131 
132  // Heapifies the subtree rooted at index i.
133  void Heapify(int i) {
134  const auto l = Left(i);
135  const auto r = Right(i);
136  auto largest = (l < size_ && comp_(values_[l], values_[i])) ? l : i;
137  if (r < size_ && comp_(values_[r], values_[largest])) largest = r;
138  if (largest != i) {
139  Swap(i, largest);
140  Heapify(largest);
141  }
142  }
143 
144  // Inserts (updates) element at subtree rooted at index i.
145  int Insert(const Value &value, int i) {
146  int p;
147  while (i > 0 && !comp_(values_[p = Parent(i)], value)) {
148  Swap(i, p);
149  i = p;
150  }
151  return key_[i];
152  }
153 
154  private:
155  const Compare comp_;
156 
157  std::vector<int> pos_;
158  std::vector<int> key_;
159  std::vector<Value> values_;
160  int size_;
161 };
162 
163 template <class T, class Compare>
164 constexpr int Heap<T, Compare>::kNoKey;
165 
166 } // namespace fst
167 
168 #endif // FST_HEAP_H_
const Compare & GetCompare() const
Definition: heap.h:97
Heap(Compare comp=Compare())
Definition: heap.h:37
void Clear()
Definition: heap.h:87
bool Empty() const
Definition: heap.h:85
const Value & Get(int key) const
Definition: heap.h:82
static constexpr int kNoKey
Definition: heap.h:34
const Value & Top() const
Definition: heap.h:79
int Size() const
Definition: heap.h:89
Value Pop()
Definition: heap.h:69
int Insert(const Value &value)
Definition: heap.h:40
void Reserve(int size)
Definition: heap.h:91
void Update(int key, const Value &value)
Definition: heap.h:57