Skip to content

leftist_heap.hpp

SECTIONData Structure INCLUDEnoya/leftist_heap.hpp

提供可快速合并的优先队列；题目频繁合并两堆元素并取出极值时使用。

Complexity: Time: O(log n) push/pop/meld. Space: O(n) nodes and O(log n) stack.

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(log n) push/pop/meld.
/// Space: O(n) nodes and O(log n) stack.

#include <cassert>
#include <functional>
#include <utility>

namespace noya {

/// @brief Meldable leftist heap with O(log n) push, pop, and heap merging.
template <class T, class Compare = std::less<T>> struct leftist_heap {
  struct node {
    T val;
    node *ls = nullptr;
    node *rs = nullptr;
    int rk = 1;
  };

  node *rt = nullptr;
  Compare cmp{};

  leftist_heap() = default;
  leftist_heap(const leftist_heap &) = delete;
  leftist_heap &operator=(const leftist_heap &) = delete;
  leftist_heap(leftist_heap &&rhs) noexcept
      : rt(std::exchange(rhs.rt, nullptr)), cmp(std::move(rhs.cmp)) {}
  leftist_heap &operator=(leftist_heap &&rhs) noexcept {
    if (this != &rhs) {
      clear(rt);
      rt = std::exchange(rhs.rt, nullptr);
      cmp = std::move(rhs.cmp);
    }
    return *this;
  }
  ~leftist_heap() { clear(rt); }

  bool empty() const { return rt == nullptr; }
  const T &top() const {
    assert(rt != nullptr);
    return rt->val;
  }
  void push(const T &val) { rt = meld(rt, new node{val}); }
  void push(T &&val) { rt = meld(rt, new node{std::move(val)}); }
  void pop() {
    assert(rt != nullptr);
    node *old = rt;
    rt = meld(rt->ls, rt->rs);
    delete old;
  }
  void merge(leftist_heap &rhs) {
    if (this != &rhs) {
      rt = meld(rt, std::exchange(rhs.rt, nullptr));
    }
  }

private:
  int rank(node *cur) const { return cur == nullptr ? 0 : cur->rk; }
  node *meld(node *a, node *b) {
    if (a == nullptr || b == nullptr) {
      return a == nullptr ? b : a;
    }
    if (cmp(b->val, a->val)) {
      std::swap(a, b);
    }
    a->rs = meld(a->rs, b);
    if (rank(a->ls) < rank(a->rs)) {
      std::swap(a->ls, a->rs);
    }
    a->rk = rank(a->rs) + 1;
    return a;
  }
  void clear(node *cur) {
    if (cur != nullptr) {
      clear(cur->ls);
      clear(cur->rs);
      delete cur;
    }
  }
};

} // namespace noya

#ifndef NOYA_LEFTIST_HEAP_HPP
#define NOYA_LEFTIST_HEAP_HPP 1

/// @complexity Time: O(log n) push/pop/meld.
/// Space: O(n) nodes and O(log n) stack.

#include <cassert>
#include <functional>
#include <utility>

namespace noya {

/// @brief Meldable leftist heap with O(log n) push, pop, and heap merging.
template <class T, class Compare = std::less<T>> struct leftist_heap {
  struct node {
    T val;
    node *ls = nullptr;
    node *rs = nullptr;
    int rk = 1;
  };

  node *rt = nullptr;
  Compare cmp{};

  leftist_heap() = default;
  leftist_heap(const leftist_heap &) = delete;
  leftist_heap &operator=(const leftist_heap &) = delete;
  leftist_heap(leftist_heap &&rhs) noexcept
      : rt(std::exchange(rhs.rt, nullptr)), cmp(std::move(rhs.cmp)) {}
  leftist_heap &operator=(leftist_heap &&rhs) noexcept {
    if (this != &rhs) {
      clear(rt);
      rt = std::exchange(rhs.rt, nullptr);
      cmp = std::move(rhs.cmp);
    }
    return *this;
  }
  ~leftist_heap() { clear(rt); }

  bool empty() const { return rt == nullptr; }
  const T &top() const {
    assert(rt != nullptr);
    return rt->val;
  }
  void push(const T &val) { rt = meld(rt, new node{val}); }
  void push(T &&val) { rt = meld(rt, new node{std::move(val)}); }
  void pop() {
    assert(rt != nullptr);
    node *old = rt;
    rt = meld(rt->ls, rt->rs);
    delete old;
  }
  void merge(leftist_heap &rhs) {
    if (this != &rhs) {
      rt = meld(rt, std::exchange(rhs.rt, nullptr));
    }
  }

private:
  int rank(node *cur) const { return cur == nullptr ? 0 : cur->rk; }
  node *meld(node *a, node *b) {
    if (a == nullptr || b == nullptr) {
      return a == nullptr ? b : a;
    }
    if (cmp(b->val, a->val)) {
      std::swap(a, b);
    }
    a->rs = meld(a->rs, b);
    if (rank(a->ls) < rank(a->rs)) {
      std::swap(a->ls, a->rs);
    }
    a->rk = rank(a->rs) + 1;
    return a;
  }
  void clear(node *cur) {
    if (cur != nullptr) {
      clear(cur->ls);
      clear(cur->rs);
      delete cur;
    }
  }
};

} // namespace noya

#endif // NOYA_LEFTIST_HEAP_HPP

#include <cassert>
#include <functional>
#include <utility>

/// @complexity Time: O(log n) push/pop/meld.
/// Space: O(n) nodes and O(log n) stack.

namespace noya {

/// @brief Meldable leftist heap with O(log n) push, pop, and heap merging.
template <class T, class Compare = std::less<T>> struct leftist_heap {
  struct node {
    T val;
    node *ls = nullptr;
    node *rs = nullptr;
    int rk = 1;
  };

  node *rt = nullptr;
  Compare cmp{};

  leftist_heap() = default;
  leftist_heap(const leftist_heap &) = delete;
  leftist_heap &operator=(const leftist_heap &) = delete;
  leftist_heap(leftist_heap &&rhs) noexcept
      : rt(std::exchange(rhs.rt, nullptr)), cmp(std::move(rhs.cmp)) {}
  leftist_heap &operator=(leftist_heap &&rhs) noexcept {
    if (this != &rhs) {
      clear(rt);
      rt = std::exchange(rhs.rt, nullptr);
      cmp = std::move(rhs.cmp);
    }
    return *this;
  }
  ~leftist_heap() { clear(rt); }

  bool empty() const { return rt == nullptr; }
  const T &top() const {
    assert(rt != nullptr);
    return rt->val;
  }
  void push(const T &val) { rt = meld(rt, new node{val}); }
  void push(T &&val) { rt = meld(rt, new node{std::move(val)}); }
  void pop() {
    assert(rt != nullptr);
    node *old = rt;
    rt = meld(rt->ls, rt->rs);
    delete old;
  }
  void merge(leftist_heap &rhs) {
    if (this != &rhs) {
      rt = meld(rt, std::exchange(rhs.rt, nullptr));
    }
  }

private:
  int rank(node *cur) const { return cur == nullptr ? 0 : cur->rk; }
  node *meld(node *a, node *b) {
    if (a == nullptr || b == nullptr) {
      return a == nullptr ? b : a;
    }
    if (cmp(b->val, a->val)) {
      std::swap(a, b);
    }
    a->rs = meld(a->rs, b);
    if (rank(a->ls) < rank(a->rs)) {
      std::swap(a->ls, a->rs);
    }
    a->rk = rank(a->rs) + 1;
    return a;
  }
  void clear(node *cur) {
    if (cur != nullptr) {
      clear(cur->ls);
      clear(cur->rs);
      delete cur;
    }
  }
};

} // namespace noya