message: Optimization: skip unnecessary std::push_heap operation: see added comments.
diff: @@ -76,9 +76,8 @@ TfLiteStatus ResizeOutput(TfLiteContext* context, TfLiteNode* node) {
  return kTfLiteOk;
  }
  -// The class that collects top indexes of k values. Based on template
  -// tensorflow::gtl::TopN<> but, for optimization,
  -// it re-uses the same container.
  +// Class that collects indices of top k values. Based on template
  +// tensorflow::gtl::TopN<> but, for optimization, it re-uses the same container.
  template <typename T>
  class TopContainer {
  public:
  @@ -100,8 +99,21 @@ class TopContainer {
  std::pop_heap(container_.begin(), container_.end(), comparator);
  }
  } else if (comparator(a, container_.front())) {
  + // Due to how we defined comparator / compare_fun, container_.front()
  + // contains the index of the smallest of the top-k elements seen so far.
  + //
  + // If control reaches this point, we know that the current index a
  + // corresponds to an element which is bigger than the smallest of the
  + // top-k elements seen so far. Hence, we have to update the indices of
  + // the top-k elements, by removing the index of the smallest top-k
  + // element, adding a, and making sure container_[0:k] is still a heap.
  +
  + // Store index a into container_[k].
  container_.back() = a;
  - std::push_heap(container_.begin(), container_.end(), comparator);
  +
  + // Swap container_[0] and container_[k], and rearrange elements from
  + // container_[0,k) such that they are a heap according to comparator. For
  + // more info, see https://en.cppreference.com/w/cpp/algorithm/pop_heap.
  std::pop_heap(container_.begin(), container_.end(), comparator);
  }
  }
  @@ -109,6 +121,9 @@ class TopContainer {
  const std::vector<int32>& sorted_result() {
  auto comparator = [this](int32 a, int32 b) { return compare_fun(a, b); };
  if (container_.size() <= k_) {
  + // Note: due to the way we defined compare_fun (see comments for that
  + // function) std::sort puts the indices from container_ in decreasing
  + // order of the corresponding elements.
  std::sort(container_.begin(), container_.end(), comparator);
  } else {
  std::sort_heap(container_.begin(), container_.end() - 1, comparator);
  @@ -118,10 +133,22 @@ class TopContainer {
  }
  private:
  - int32 k_;
  + const int32 k_;
  +
  + // container_[0,k) holds the indices of the largest k elements from values_
  + // seen so far and are maintained in a min-heap order: container_.front() is
  + // the index of the smallest of the top-k elements see so far.
  + //
  + // container_[k] is used as temporary space (not part of the min-heap).
  std::vector<int32> container_;
  +
  const T* values_ = nullptr;
  + // Compares indices a and b based on the corresponding elements from values_.
  + //
  + // Intuitively, compare_fun(a, b) returns true iff values_[b] < values_[a]
  + // (notice the inversion of direction, not a typo); ties (==) are broken in
  + // favor of earlier elements (i.e., a < b).
  bool compare_fun(int32 a, int32 b) const {
  if (values_[b] < values_[a]) {
  return true;
  