Leftist-Heap (structure/heap/leftist-heap.hpp)

View this file on GitHub
Last update: 2024-04-24 02:34:04+09:00
Include: #include "structure/heap/leftist-heap.hpp"

Verified with

Code

/**
 * @brief Leftist-Heap
 */
template< typename T, bool isMin = true >
struct LeftistHeap {
  struct Node {
    Node *l, *r;
    int s;
    T key;
    int idx;

    explicit Node(const T &key, int idx) : key(key), s(1), l(nullptr), r(nullptr), idx(idx) {}
  };

  LeftistHeap() = default;

  virtual Node *clone(Node *t) {
    return t;
  }

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

  Node *meld(Node *a, Node *b) {
    if(!a || !b) return a ? a : b;
    if((a->key < b->key) ^ isMin) swap(a, b);
    a = clone(a);
    a->r = meld(a->r, b);
    if(!a->l || a->l->s < a->r->s) swap(a->l, a->r);
    a->s = (a->r ? a->r->s : 0) + 1;
    return a;
  }

  Node *push(Node *t, const T &key, int idx = -1) {
    return meld(t, alloc(key, idx));
  }

  Node *pop(Node *t) {
    assert(t != nullptr);
    return meld(t->l, t->r);
  }

  Node *make_root() {
    return nullptr;
  }
};

#line 1 "structure/heap/leftist-heap.hpp"
/**
 * @brief Leftist-Heap
 */
template< typename T, bool isMin = true >
struct LeftistHeap {
  struct Node {
    Node *l, *r;
    int s;
    T key;
    int idx;

    explicit Node(const T &key, int idx) : key(key), s(1), l(nullptr), r(nullptr), idx(idx) {}
  };

  LeftistHeap() = default;

  virtual Node *clone(Node *t) {
    return t;
  }

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

  Node *meld(Node *a, Node *b) {
    if(!a || !b) return a ? a : b;
    if((a->key < b->key) ^ isMin) swap(a, b);
    a = clone(a);
    a->r = meld(a->r, b);
    if(!a->l || a->l->s < a->r->s) swap(a->l, a->r);
    a->s = (a->r ? a->r->s : 0) + 1;
    return a;
  }

  Node *push(Node *t, const T &key, int idx = -1) {
    return meld(t, alloc(key, idx));
  }

  Node *pop(Node *t) {
    assert(t != nullptr);
    return meld(t->l, t->r);
  }

  Node *make_root() {
    return nullptr;
  }
};