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