pairing_heap.hpp

#pragma once
 
#include <functional>
#include <string>
#include <vector>
 
namespace cplib {
 
namespace impl {
 
// Left-child right-sibling representation of the pairing heap
template <typename T>
struct PairingHeapNode {
  PairingHeapNode(const T& val) : _val(val), left(nullptr), right(nullptr), parent(nullptr) {}
 
  PairingHeapNode(T&& val) : _val(std::move(val)), left(nullptr), right(nullptr), parent(nullptr) {}
 
  template <typename... Args, typename = decltype(T(std::declval<Args>()...))>
  PairingHeapNode(Args&&... args) : _val(std::forward<Args>(args)...), left(nullptr), right(nullptr), parent(nullptr) {}
 
  // Add `child` as the youngest child (first in the sibling list). Both `this` and `child` must be root nodes.
  void adopt(PairingHeapNode* child) {
    if (!child) {
      return;
    }
    child->right = left;
    if (left) {
      left->parent = child;
    }
    left = child;
    child->parent = this;
  }
 
  // Deatch this node and its subtree from its parent, so that it becomes an independent root node.
  // Must only be called on non-root nodes.
  void detach() {
    if (parent->left == this) {
      parent->left = right;
    } else {
      parent->right = right;
    }
    if (right) {
      right->parent = parent;
    }
    right = nullptr;
    parent = nullptr;
  }
 
  T _val;
  PairingHeapNode *left, *right, *parent;
};
 
}  // namespace impl
 
template <typename T, typename Comp = std::less<T>>
struct PairingHeap {
 public:
  using size_type = std::size_t;
  using node_type = impl::PairingHeapNode<T>;
 
  PairingHeap() : root(nullptr), _size(0), comp() {}
 
  struct iterator {
    const T& operator*() { return node->_val; }
 
    const T* operator->() { return &node->_val; }
 
    bool operator==(const iterator& rhs) const { return node == rhs.node; }
 
    bool operator!=(const iterator& rhs) const { return node != rhs.node; }
 
   private:
    friend PairingHeap;
    node_type* node;
 
    iterator(node_type* node) : node(node) {}
  };
 
  size_type size() const { return _size; }
 
  bool empty() const { return !root; }
 
  const T& top() { return root->_val; }
 
  iterator begin() { return iterator(root); }
 
  iterator end() { return iterator(nullptr); }
 
  iterator push(const T& t) {
    auto node = new node_type(t);
    _merge_with(node, 1);
    return iterator(node);
  }
 
  iterator push(T&& t) {
    auto node = new node_type(std::move(t));
    _merge_with(node, 1);
    return iterator(node);
  }
 
  template <typename... Args>
  iterator emplace(Args&&... args) {
    auto node = new node_type(std::forward<Args>(args)...);
    _merge_with(node, 1);
    return iterator(node);
  }
 
  void pop() {
    _size--;
    if (!root->left) {
      delete root;
      root = nullptr;
      return;
    }
    auto* curr = root->left;
    node_type* last = nullptr;
    delete root;
    // Merge in pairs, following the forward (`right`) linked list, and creating a backward (`parent`) linked list
    while (true) {
      auto next = curr->right;
      if (!next) {
        curr->parent = last;
        last = curr;
        break;
      }
      auto next_next = next->right;
      curr->parent = nullptr;
      curr->right = nullptr;
      next->parent = nullptr;
      next->right = nullptr;
      auto merged = _merge_node(curr, next);
      merged->parent = last;
      last = merged;
      if (!next_next) {
        break;
      }
      curr = next_next;
    }
    // Merge from the back, following the backward (`parent`) linked list just created.
    auto prev = last->parent;
    while (prev) {
      auto prev_prev = prev->parent;
      last->parent = nullptr;
      prev->parent = nullptr;
      last = _merge_node(last, prev);
      last->parent = prev_prev;
      prev = prev_prev;
    }
    root = last;
  }
 
  void merge(PairingHeap&& other) {
    _merge_with(other.root, other.size());
    other._size = 0;
    other.root = nullptr;
  }
 
  void decrease_key(iterator it, const T& new_key) {
    if (it.node != root) {
      it.node->detach();
      it.node->_val = new_key;
      _merge_with(it.node, 0);
    } else {
      root->_val = new_key;
    }
  }
 
  void erase(iterator it) {
    if (it.node != root) {
      it.node->detach();
      it.node->adopt(root);
      root = it.node;
    }
    pop();
  }
 
 private:
  node_type* root;
  size_type _size;
  Comp comp;
 
  node_type* _merge_node(node_type* node1, node_type* node2) {
    if (!node1) {
      return node2;
    } else if (!node2) {
      return node1;
    }
    if (comp(node1->_val, node2->_val)) {
      std::swap(node1, node2);
    }
    node2->adopt(node1);
    return node2;
  }
 
  void _merge_with(node_type* other, size_type size_incr) {
    root = _merge_node(root, other);
    _size += size_incr;
  }
};
 
}  // namespace cplib