45 template <
class T,
class Compare>
53 explicit Heap(Compare comp = Compare()) : comp_(comp), size_(0) {}
57 if (size_ < values_.size()) {
58 values_[size_] = value;
59 pos_[key_[size_]] = size_;
61 values_.push_back(value);
62 pos_.push_back(size_);
63 key_.push_back(size_);
66 return Insert(value, size_ - 1);
74 const auto i = pos_[key];
75 const bool is_better = comp_(value, values_[Parent(i)]);
87 Value top = values_.front();
98 return values_.front();
104 return values_[pos_[key]];
108 bool Empty()
const {
return size_ == 0; }
112 int Size()
const {
return size_; }
115 values_.reserve(size);
127 static int Left(
int i) {
128 return 2 * (i + 1) - 1;
132 static int Right(
int i) {
137 static int Parent(
int i) {
147 void Swap(
int j,
int k) {
148 const auto tkey = key_[j];
149 pos_[key_[j] = key_[k]] = j;
150 pos_[key_[k] = tkey] = k;
152 swap(values_[j], values_[k]);
156 void Heapify(
int i) {
157 const auto l = Left(i);
158 const auto r = Right(i);
159 auto largest = (l < size_ && comp_(values_[l], values_[i])) ? l : i;
160 if (r < size_ && comp_(values_[r], values_[largest])) largest = r;
170 while (i > 0 && !comp_(values_[p = Parent(i)], value)) {
180 std::vector<int> pos_;
181 std::vector<int> key_;
182 std::vector<Value> values_;
188 #endif // FST_HEAP_H_
const Compare & GetCompare() const
Heap(Compare comp=Compare())
const Value & Get(int key) const
static constexpr int kNoKey
const Value & Top() const
int Insert(const Value &value)
void Update(int key, const Value &value)