Luzhiled's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub ei1333/library

:heavy_check_mark: test/unittest/basic-heaps.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <cassert>
#include <queue>
#include <random>
#include <vector>

#include "../../structure/heap/erasable-heap.hpp"
#include "../../structure/heap/leftist-heap.hpp"
#include "../../structure/heap/persistent-leftist-heap.hpp"
#include "../../structure/heap/skew-heap.hpp"

int main() {
  {
    erasable_heap<int> heap;
    heap.push(3);
    heap.push(1);
    heap.push(5);
    heap.push(5);
    assert(heap.top() == 5);
    heap.erase(5);
    assert(heap.top() == 5);
    heap.pop();
    assert(heap.top() == 3);
    heap.erase(1);
    heap.pop();
    assert(heap.empty());
  }

  {
    LeftistHeap<int> heap;
    auto root = heap.make_root();
    std::priority_queue<int, std::vector<int>, std::greater<int>> expected;
    std::mt19937 rng(123456789);
    for (int iteration = 0; iteration < 5000; iteration++) {
      if (expected.empty() || rng() % 3 != 0) {
        int value = (int)(rng() % 201) - 100;
        root = heap.push(root, value);
        expected.push(value);
      } else {
        assert(root->key == expected.top());
        root = heap.pop(root);
        expected.pop();
      }
      if (!expected.empty()) assert(root->key == expected.top());
    }
  }

  {
    PersistentLeftistHeap<int> heap;
    auto base = heap.make_root();
    base = heap.push(base, 3);
    base = heap.push(base, 7);
    auto first = heap.push(base, 1);
    auto second = heap.push(base, 5);
    assert(base->key == 3);
    assert(first->key == 1);
    assert(second->key == 3);
    second = heap.pop(second);
    assert(second->key == 5);
    assert(base->key == 3);
  }

  {
    SkewHeap<long long> heap;
    auto root = heap.make_root();
    root = heap.push(root, 5);
    root = heap.push(root, 2);
    root = heap.push(root, 8);
    assert(root->key == 2);
    root = heap.add(root, 10);
    assert(root->key == 12);
    root = heap.pop(root);
    assert(root->key == 15);
  }
}

#line 1 "test/unittest/basic-heaps.test.cpp"
// competitive-verifier: STANDALONE

#include <cassert>
#include <queue>
#include <random>
#include <vector>

#line 2 "structure/heap/erasable-heap.hpp"

#line 4 "structure/heap/erasable-heap.hpp"
#include <functional>
#line 6 "structure/heap/erasable-heap.hpp"
#include <utility>
#line 8 "structure/heap/erasable-heap.hpp"

template <typename T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class erasable_heap {
  std::priority_queue<T, Container, Compare> base, erased;

  void normalize() {
    while (true) {
      if (base.empty()) break;
      if (erased.empty()) break;
      if (base.top() != erased.top()) break;
      base.pop();
      erased.pop();
    }
  }

 public:
  bool empty() const { return base.empty(); }

  const T& top() const {
    assert(!empty());
    return base.top();
  }

  void push(T val) {
    base.push(std::move(val));
    normalize();
  }

  template <class... Args>
  void emplace(Args... args) {
    base.emplace(args...);
    normalize();
  }

  void pop() {
    assert(!empty());
    base.pop();
    normalize();
  }

  void erase(T val) {
    erased.push(std::move(val));
    normalize();
  }
};
#line 2 "structure/heap/leftist-heap.hpp"

#line 5 "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)
        : l(nullptr), r(nullptr), s(1), key(key), 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) std::swap(a, b);
    a = clone(a);
    a->r = meld(a->r, b);
    if (!a->l || a->l->s < a->r->s) std::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 2 "structure/heap/persistent-leftist-heap.hpp"

#line 4 "structure/heap/persistent-leftist-heap.hpp"

/**
 * @brief Persistent-Leftist-Heap
 */
template <typename T, bool isMin = true>
struct PersistentLeftistHeap : LeftistHeap<T, isMin> {
  using Node = typename LeftistHeap<T, isMin>::Node;

  Node* clone(Node* t) override { return new Node(*t); }
};
#line 2 "structure/heap/skew-heap.hpp"

#line 5 "structure/heap/skew-heap.hpp"

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

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

  SkewHeap() = default;

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

  Node* propagate(Node* t) {
    if (t && t->lazy != 0) {
      if (t->l) t->l->lazy += t->lazy;
      if (t->r) t->r->lazy += t->lazy;
      t->key += t->lazy;
      t->lazy = 0;
    }
    return t;
  }

  Node* meld(Node* x, Node* y) {
    propagate(x), propagate(y);
    if (!x || !y) return x ? x : y;
    if ((x->key < y->key) ^ isMin) std::swap(x, y);
    x->r = meld(y, x->r);
    std::swap(x->l, x->r);
    return x;
  }

  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* add(Node* t, const T& lazy) {
    if (t) {
      t->lazy += lazy;
      propagate(t);
    }
    return t;
  }

  Node* make_root() { return nullptr; }
};
#line 12 "test/unittest/basic-heaps.test.cpp"

int main() {
  {
    erasable_heap<int> heap;
    heap.push(3);
    heap.push(1);
    heap.push(5);
    heap.push(5);
    assert(heap.top() == 5);
    heap.erase(5);
    assert(heap.top() == 5);
    heap.pop();
    assert(heap.top() == 3);
    heap.erase(1);
    heap.pop();
    assert(heap.empty());
  }

  {
    LeftistHeap<int> heap;
    auto root = heap.make_root();
    std::priority_queue<int, std::vector<int>, std::greater<int>> expected;
    std::mt19937 rng(123456789);
    for (int iteration = 0; iteration < 5000; iteration++) {
      if (expected.empty() || rng() % 3 != 0) {
        int value = (int)(rng() % 201) - 100;
        root = heap.push(root, value);
        expected.push(value);
      } else {
        assert(root->key == expected.top());
        root = heap.pop(root);
        expected.pop();
      }
      if (!expected.empty()) assert(root->key == expected.top());
    }
  }

  {
    PersistentLeftistHeap<int> heap;
    auto base = heap.make_root();
    base = heap.push(base, 3);
    base = heap.push(base, 7);
    auto first = heap.push(base, 1);
    auto second = heap.push(base, 5);
    assert(base->key == 3);
    assert(first->key == 1);
    assert(second->key == 3);
    second = heap.pop(second);
    assert(second->key == 5);
    assert(base->key == 3);
  }

  {
    SkewHeap<long long> heap;
    auto root = heap.make_root();
    root = heap.push(root, 5);
    root = heap.push(root, 2);
    root = heap.push(root, 8);
    assert(root->key == 2);
    root = heap.add(root, 10);
    assert(root->key == 12);
    root = heap.pop(root);
    assert(root->key == 15);
  }
}
Back to top page