Skew Heap
(data-structure/skew-heap.hpp)

• View this file on GitHub
• Last update: 2021-02-04 22:39:44+09:00
• Include: #include "data-structure/skew-heap.hpp"

Skew Heap

Skew Heapを実装したライブラリ。

概要

Skew Heapとは、ヒープ同士のマージ(融合, meld)やヒープ全体に定数を加算する操作を高速に行うことが出来るヒープである。アルゴリズム自体は一読して理解できる程度に簡潔だが計算量解析は難しい。(参考)

ヒープ全体への定数の加算を諦める代わりに特定のノードの値を高速に更新する機能をつけることが出来て、ダイクストラ法の定数倍高速化に利用される。

使い方

平衡二分木などのライブラリと同様に根のノードをポインタで持つ形で管理する。push, popなどの操作を行ったときに根が変化するので、返り値で新しい根を返す。

根に最小の値が入っていて、p->key + p->addでkeyを、p->idxでkeyに関連する情報を取得することが出来る。

• SkewHeap<T, isMin = true>: 型Tをkeyの型として最小値が根になるヒープ。isMinをFalseにすると最大値が根になる。
• Ptr push(Ptr x, const T& key, int idx): 根をxとするヒープに(key, idx)を挿入して新しい根へのポインタを返す。
• Ptr pop(Ptr x): 根のノードを削除して新しい根へのポインタを返す。
• Ptr alloc(const T& key, int idx): (key, idx)を持ったノードを新しく作成して、ポインタを返す。
• meld(Ptr x, Ptr y): xとyを融合して新たな根のポインタを返す。

Required by

• graph/minimum-cost-arborescence.hpp

Verified with

• verify/verify-yosupo-graph/yosupo-directed-mst.test.cpp

Code

#pragma once

template <typename T, bool isMin = true>
struct SkewHeap {
  struct Node {
    T key, laz;
    Node *l, *r;
    int idx;
    Node() = default;
    Node(const T &k, int i = -1)
        : key(k), laz(0), l(nullptr), r(nullptr), idx(i) {}
  };
  using Ptr = Node *;

  static void propagate(Ptr x) {
    if (x->laz == 0) return;
    if (x->l) x->l->laz += x->laz;
    if (x->r) x->r->laz += x->laz;
    x->key += x->laz;
    x->laz = 0;
  }

  static Ptr meld(Ptr x, Ptr y) {
    if (!x || !y) return x ? x : y;
    if (!comp(x, y)) swap(x, y);
    propagate(x);
    x->r = meld(x->r, y);
    swap(x->l, x->r);
    return x;
  }

  static Ptr alloc(const T &key, int idx = -1) { return new Node(key, idx); }

  static Ptr pop(Ptr x) {
    propagate(x);
    return meld(x->l, x->r);
  }

  static Ptr push(Ptr x, const T &key, int idx = -1) {
    return meld(x, alloc(key, idx));
  }

  static void apply(Ptr x, const T &laz) {
    x->laz += laz;
    propagate(x);
  }

 private:
  static inline bool comp(Ptr x, Ptr y) {
    if constexpr (isMin) {
      return x->key + x->laz < y->key + y->laz;
    } else {
      return x->key + x->laz > y->key + y->laz;
    }
  }
};

/**
 * @brief Skew Heap
 * @docs docs/data-structure/skew-heap.md
 */

#line 2 "data-structure/skew-heap.hpp"

template <typename T, bool isMin = true>
struct SkewHeap {
  struct Node {
    T key, laz;
    Node *l, *r;
    int idx;
    Node() = default;
    Node(const T &k, int i = -1)
        : key(k), laz(0), l(nullptr), r(nullptr), idx(i) {}
  };
  using Ptr = Node *;

  static void propagate(Ptr x) {
    if (x->laz == 0) return;
    if (x->l) x->l->laz += x->laz;
    if (x->r) x->r->laz += x->laz;
    x->key += x->laz;
    x->laz = 0;
  }

  static Ptr meld(Ptr x, Ptr y) {
    if (!x || !y) return x ? x : y;
    if (!comp(x, y)) swap(x, y);
    propagate(x);
    x->r = meld(x->r, y);
    swap(x->l, x->r);
    return x;
  }

  static Ptr alloc(const T &key, int idx = -1) { return new Node(key, idx); }

  static Ptr pop(Ptr x) {
    propagate(x);
    return meld(x->l, x->r);
  }

  static Ptr push(Ptr x, const T &key, int idx = -1) {
    return meld(x, alloc(key, idx));
  }

  static void apply(Ptr x, const T &laz) {
    x->laz += laz;
    propagate(x);
  }

 private:
  static inline bool comp(Ptr x, Ptr y) {
    if constexpr (isMin) {
      return x->key + x->laz < y->key + y->laz;
    } else {
      return x->key + x->laz > y->key + y->laz;
    }
  }
};

/**
 * @brief Skew Heap
 * @docs docs/data-structure/skew-heap.md
 */

Back to top page