1// heap.h
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15//
16// \file
17// Implementation of a heap as in STL, but allows tracking positions
18// in heap using a key. The key can be used to do an in place update of
19// values in the heap.
20
21#ifndef FST_LIB_HEAP_H__
22#define FST_LIB_HEAP_H__
23
24#include <functional>
25#include <vector>
26
27namespace fst {
28
29//
30// \class Heap
31// \brief A templated heap implementation that support in place update
32//        of values.
33//
34// The templated heap implementation is a little different from the
35// STL priority_queue and the *_heap operations in STL. The heap
36// supports indexing of values in the heap via an associated key.
37//
38// Each value is internally associated with a key which is returned
39// to the calling functions on heap insert. This key can be used
40// to later update the specific value in the heap.
41//
42// \param T the element type of the hash, can be POD, Data or Ptr to Data
43// \param Compare Comparison class for determing min-heapness of max-heapness
44//
45static const int kNoKey = -1;
46template <class T, class Compare>
47class Heap {
48 public:
49
50  // initialize with a specific comparator
51  Heap(Compare comp) : comp_(comp), size_(0) { }
52
53  // Create a heap with initial size of internal arrays of 1024
54  Heap() : size_(0) { }
55
56  ~Heap() { }
57
58  // insert a value into the heap
59  int Insert(const T& val) {
60    if (size_ < (int)A_.size()) {
61      A_[size_] = val;
62      pos_[key_[size_]] = size_;
63    } else {
64      A_.push_back(val);
65      pos_.push_back(size_);
66      key_.push_back(size_);
67    }
68
69    ++size_;
70    return Insert(val, size_ - 1);
71  }
72
73  // update a value at position given by the key. The pos array is first
74  // indexed by the key. The position gives the position in the heap array.
75  // Once we have the position we can then use the standard heap operations
76  // to calculate the parent and child positions.
77  void Update(int key, const T& val) {
78    int i = pos_[key];
79    if (comp_(val, A_[Parent(i)])) {
80      Insert(val, i);
81    } else {
82      A_[i] = val;
83      Heapify(i);
84    }
85  }
86
87  // pop the (best/worst) from the heap
88  T Pop() {
89    T max = A_[0];
90
91    Swap(0, size_-1);
92    size_--;
93    Heapify(0);
94    return(max);
95  }
96
97  // return value of best in heap
98  T Top() const {
99    return A_[0];
100  }
101
102  // check if the heap is empty
103  bool Empty() const {
104    return(size_ == 0);
105  }
106
107  void Clear() {
108    size_ = 0;
109  }
110
111
112  //
113  // The following protected routines is used in a supportive role
114  // for managing the heap and keeping the heap properties.
115  //
116 private:
117  // compute left child of parent
118  int Left(int i) {
119    return 2*(i+1)-1;   // 0 -> 1, 1 -> 3
120  }
121
122  // compute right child of parent
123  int Right(int i) {
124    return 2*(i+1);     // 0 -> 2, 1 -> 4
125  }
126
127  // given a child compute parent
128  int Parent(int i) {
129    return (i-1)/2;     // 1 -> 0, 2 -> 0,  3 -> 1,  4-> 1
130  }
131
132  // swap a child, parent. Use to move element up/down tree
133  // note a little tricky here. When we swap we need to swap
134  //   the value
135  //   the associated keys
136  //   the position of the value in the heap
137  void Swap(int j, int k) {
138    int tkey = key_[j];
139    pos_[key_[j] = key_[k]] = j;
140    pos_[key_[k] = tkey]    = k;
141
142    T val  = A_[j];
143    A_[j]  = A_[k];
144    A_[k]  = val;
145  }
146
147
148  // heapify subtree rooted at index i.
149  void Heapify(int i) {
150    int l = Left(i);
151    int r = Right(i);
152    int largest;
153
154    if (l < size_ && comp_(A_[l], A_[i]) )
155      largest = l;
156    else
157      largest = i;
158
159    if (r < size_ && comp_(A_[r], A_[largest]) )
160      largest = r;
161
162    if (largest != i) {
163      Swap(i, largest);
164      Heapify(largest);
165    }
166  }
167
168
169  // insert(update) element at subtree rooted at index i
170  int Insert(const T& val, int i) {
171    int p;
172    while (i > 0 && !comp_(A_[p = Parent(i)], val)) {
173      Swap(i, p);
174      i = p;
175    }
176
177    return key_[i];
178  }
179
180
181 private:
182  Compare comp_;
183
184  vector<int> pos_;
185  vector<int> key_;
186  vector<T>   A_;
187  int  size_;
188
189  // DISALLOW_EVIL_CONSTRUCTORS(Heap);
190};
191
192}
193
194#endif  // FST_LIB_HEAP_H__
195