Skew-Heap (src/DataStructure/SkewHeap.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-11-02 17:27:04+09:00
• Include: #include "src/DataStructure/SkewHeap.hpp"

マージできるヒープ
apply(v): 全体に作用素vを適用

計算量

top: $O(1)$, pop, push, merge: $O(\log N)$

Depends on

• メンバの有無を判定するテンプレート 他 (src/Internal/HAS_CHECK.hpp)

Verified with

• test/aoj/ALDS1_9_C.SkewHeap.test.cpp

Code

#pragma once
#include <functional>
#include <algorithm>
#include <cstddef>
#include "src/Internal/HAS_CHECK.hpp"
template <typename T, typename Compare= std::less<T>, typename M= void> struct SkewHeap {
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(E);
 NULLPTR_OR(E);
 template <class L> using dual= std::conjunction<has_E<L>, has_mp<L>, has_cp<L>>;
 template <class tDerived> struct Node_B {
  T key;
  tDerived *ch[2];
 };
 template <bool du_, typename tEnable= void> struct Node_D: Node_B<Node_D<du_>> {};
 template <bool du_> struct Node_D<du_, typename std::enable_if_t<du_>>: Node_B<Node_D<du_>> {
  typename M::E lazy;
  bool lazy_flg= false;
 };
 using Node= Node_D<dual<M>::value>;
 using E= nullptr_or_E_t<M>;
 Node *root;
 static inline void propagate(Node *&t, const E &x) {
  if (!t) return;
  t->lazy_flg ? (M::cp(t->lazy, x), x) : (t->lazy= x);
  M::mp(t->key, x), t->lazy_flg= true;
 }
 static inline void push(Node *t) {
  if (t->lazy_flg) propagate(t->ch[0], t->lazy), propagate(t->ch[1], t->lazy), t->lazy_flg= false;
 }
 Node *merge(Node *a, Node *b) {
  if (!a || !b) return a ? a : b;
  if (Compare()(a->key, b->key)) std::swap(a, b);
  if constexpr (dual<M>::value) push(a);
  return std::swap(a->ch[0], a->ch[1]= merge(b, a->ch[1])), a;
 }
public:
 /* max heap */ SkewHeap(): root(nullptr) {}
 void push(T key) { root= merge(root, new Node{key}); }
 T pop() {
  T ret= root->key;
  if constexpr (dual<M>::value) push(root);
  return root= merge(root->ch[0], root->ch[1]), ret;
 }
 T top() { return root->key; }
 bool empty() { return !root; }
 void apply(E v) {
  static_assert(dual<M>::value, "\"apply\" is not available\n");
  propagate(root, v);
 }
 SkewHeap &operator+=(SkewHeap r) { return root= merge(root, r.root), *this; }
 SkewHeap operator+(SkewHeap r) { return SkewHeap(*this)+= r; }
};

#line 2 "src/DataStructure/SkewHeap.hpp"
#include <functional>
#include <algorithm>
#include <cstddef>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 6 "src/DataStructure/SkewHeap.hpp"
template <typename T, typename Compare= std::less<T>, typename M= void> struct SkewHeap {
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(E);
 NULLPTR_OR(E);
 template <class L> using dual= std::conjunction<has_E<L>, has_mp<L>, has_cp<L>>;
 template <class tDerived> struct Node_B {
  T key;
  tDerived *ch[2];
 };
 template <bool du_, typename tEnable= void> struct Node_D: Node_B<Node_D<du_>> {};
 template <bool du_> struct Node_D<du_, typename std::enable_if_t<du_>>: Node_B<Node_D<du_>> {
  typename M::E lazy;
  bool lazy_flg= false;
 };
 using Node= Node_D<dual<M>::value>;
 using E= nullptr_or_E_t<M>;
 Node *root;
 static inline void propagate(Node *&t, const E &x) {
  if (!t) return;
  t->lazy_flg ? (M::cp(t->lazy, x), x) : (t->lazy= x);
  M::mp(t->key, x), t->lazy_flg= true;
 }
 static inline void push(Node *t) {
  if (t->lazy_flg) propagate(t->ch[0], t->lazy), propagate(t->ch[1], t->lazy), t->lazy_flg= false;
 }
 Node *merge(Node *a, Node *b) {
  if (!a || !b) return a ? a : b;
  if (Compare()(a->key, b->key)) std::swap(a, b);
  if constexpr (dual<M>::value) push(a);
  return std::swap(a->ch[0], a->ch[1]= merge(b, a->ch[1])), a;
 }
public:
 /* max heap */ SkewHeap(): root(nullptr) {}
 void push(T key) { root= merge(root, new Node{key}); }
 T pop() {
  T ret= root->key;
  if constexpr (dual<M>::value) push(root);
  return root= merge(root->ch[0], root->ch[1]), ret;
 }
 T top() { return root->key; }
 bool empty() { return !root; }
 void apply(E v) {
  static_assert(dual<M>::value, "\"apply\" is not available\n");
  propagate(root, v);
 }
 SkewHeap &operator+=(SkewHeap r) { return root= merge(root, r.root), *this; }
 SkewHeap operator+(SkewHeap r) { return SkewHeap(*this)+= r; }
};

Back to top page