dary_heap.hpp

#pragma once
 
#include <functional>
#include <vector>
 
namespace cplib {
 
namespace impl {
 
template <typename T, typename Comp = std::less<T>, int D = 8>
struct DaryHeapNormalImpl {};
 
}  // namespace impl
 
template <typename T, typename Comp = std::less<T>, int D = 8>
struct DaryHeap {
 public:
  using size_type = std::size_t;
 
  DaryHeap() : arr_(), comp_() {}
 
  size_type size() const { return arr_.size(); }
 
  bool empty() const { return arr_.empty(); }
 
  const T& top() { return arr_.front(); }
 
  void push(const T& t) {
    arr_.push_back(t);
    sift_up_();
  }
 
  void push(T&& t) {
    arr_.push_back(std::move(t));
    sift_up_();
  }
 
  template <typename... Args>
  void emplace(Args&&... args) {
    arr_.emplace_back(std::forward<Args>(args)...);
    sift_up_();
  }
 
  void pop() {
    arr_.front() = std::move(arr_.back());
    arr_.pop_back();
    sift_down_();
  }
 
 private:
  std::vector<T> arr_;
  Comp comp_;
 
  void sift_up_() {
    size_type i = arr_.size() - 1;
    while (i > 0 && comp_(arr_[i], arr_[(i - 1) / D])) {
      std::swap(arr_[i], arr_[(i - 1) / D]);
      i = (i - 1) / D;
    }
  }
 
  void sift_down_() {
    size_type i = 0;
    while (i * D + 1 < arr_.size()) {
      size_type min_child = i * D + 1;
      for (size_type child = i * D + 2; child < std::min(i * D + (D + 1), arr_.size()); child++) {
        if (comp_(arr_[child], arr_[min_child])) {
          min_child = child;
        }
      }
      if (comp_(arr_[min_child], arr_[i])) {
        std::swap(arr_[min_child], arr_[i]);
        i = min_child;
      } else {
        break;
      }
    }
  }
};
 
}  // namespace cplib