Skew heap
(Mylib/DataStructure/Heap/skew_heap.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/2559/main.skew_heap.test.cpp

Code

#pragma once
#include <functional>
#include <utility>

namespace haar_lib {
  template <typename T, class Compare = std::less<T>>
  class skew_heap {
  public:
    using value_type = T;

  private:
    struct node {
      T val;
      node *left, *right;
      int size;
      node(const T &val) : val(val), left(nullptr), right(nullptr), size(1) {}
    };

    node *root_;
    Compare compare_;

  public:
    skew_heap() : root_(nullptr), compare_(Compare()) {}
    skew_heap(const Compare &compare_) : root_(nullptr), compare_(compare_) {}

  protected:
    node *meld(node *a, node *b) {
      if (not a) return b;
      if (not b) return a;

      if (compare_(a->val, b->val)) std::swap(a, b);

      a->size += b->size;
      a->right = meld(a->right, b);
      std::swap(a->left, a->right);

      return a;
    }

  public:
    void meld(skew_heap &heap) {
      root_      = meld(root_, heap.root_);
      heap.root_ = nullptr;
    }
    void push(const T &val) { root_ = meld(root_, new node(val)); }
    const T &top() const { return root_->val; }
    void pop() {
      node *temp = root_;
      root_      = meld(root_->left, root_->right);
      delete temp;
    }
    bool empty() const { return root_ == nullptr; }
    size_t size() const { return root_ ? root_->size : 0; }
  };
}  // namespace haar_lib

#line 2 "Mylib/DataStructure/Heap/skew_heap.cpp"
#include <functional>
#include <utility>

namespace haar_lib {
  template <typename T, class Compare = std::less<T>>
  class skew_heap {
  public:
    using value_type = T;

  private:
    struct node {
      T val;
      node *left, *right;
      int size;
      node(const T &val) : val(val), left(nullptr), right(nullptr), size(1) {}
    };

    node *root_;
    Compare compare_;

  public:
    skew_heap() : root_(nullptr), compare_(Compare()) {}
    skew_heap(const Compare &compare_) : root_(nullptr), compare_(compare_) {}

  protected:
    node *meld(node *a, node *b) {
      if (not a) return b;
      if (not b) return a;

      if (compare_(a->val, b->val)) std::swap(a, b);

      a->size += b->size;
      a->right = meld(a->right, b);
      std::swap(a->left, a->right);

      return a;
    }

  public:
    void meld(skew_heap &heap) {
      root_      = meld(root_, heap.root_);
      heap.root_ = nullptr;
    }
    void push(const T &val) { root_ = meld(root_, new node(val)); }
    const T &top() const { return root_->val; }
    void pop() {
      node *temp = root_;
      root_      = meld(root_->left, root_->right);
      delete temp;
    }
    bool empty() const { return root_ == nullptr; }
    size_t size() const { return root_ ? root_->size : 0; }
  };
}  // namespace haar_lib

Back to top page