Is paring heap a better structure for intrusive heap?

[SchrodingerZhu]

The following code implements a variant of paring heap:

template <typename T, T* T::*Next, T* T::*Parent, T* T::*Children, typename Key, Key T::*SortKey>
class intrusive_paring_heap {
 public:
  intrusive_paring_heap() noexcept : root_(nullptr) {}

  bool empty() const noexcept {
    return root_ == nullptr;
  }

  T* top() const noexcept {
    assert(!empty());
    return root_;
  }

  void insert(T* item) noexcept {
    root_ = merge(root_, item);
  }

  T* pop() noexcept {
    assert(!empty());
    auto item = root_;
    T *x, *y, *list = nullptr;
    while ((x = root_->*Children)) {
      if ((root_->*Children = y = x->*Next))
        root_->*Children = root_->*Children->*Next;
      list = push_front(list, merge(x, y));
    }
    x = nullptr;
    while ((y = list)) {
      list = list->*Next;
      x = merge(x, y);
    }
    root_ = x;
    if(root_) root_->*Parent = nullptr;
    item->*Children = item->*Parent = item->*Next = nullptr;
    return item;
  }

  void remove(T* item) noexcept {
    T* parent = item->*Parent;
    if (parent == nullptr) {
      pop();
    }
    else {
      parent->*Children = remove_node(parent->*Children, item);
      if (item->*Children) {
        item->*Children->*Parent = nullptr;
        root_ = merge(root_, item->*Children);
      }
      item->*Children = item->*Parent = item->*Next = nullptr;
    }
  }

 private:
  T* root_;

  static inline T* push_front(T* list, T* x) noexcept {
    x->*Next = list;
    return x;
  }

  static inline T* remove_node(T* list, T* x) noexcept {
    T* p = list;
    if (x == list) return x->*Next;
    while (p && p->*Next != x) p = p->*Next;
    if (p) p->*Next = x->*Next;
    return list;
  }

  static inline T* merge(T* h1, T* h2) noexcept {
    if (!h1) return h2;
    if (!h2) return h1;
    if (h2->*SortKey < h1->*SortKey) std::swap(h1, h2);
    h2->*Next = h1->*Children;
    h1->*Children = h2;
    h2->*Parent = h1;
    h1->*Next = nullptr;
    return h1;
  }
};

However, it seems to have much more branch conditions; and it requires an extra slot of pointer and nullptr initialisation.

(It passes all tests but I didn't test more cases. Also, I didn't whether checkout the binary layout is good enough.)

[lewissbaker]

Thanks for the suggestion. The intrusive heap structure is indeed rather naive and placeholder at the moment and won't scale well to large numbers of timers, but was simple to get up and running

I'll need to do some more analysis of this data-structure to determine whether it makes sense to replace what we have with this.

The other data-structure I've been considering adopting for managing priority queues of timers was a hashed hierarchical wheel timer structure, like the one used in folly. It has a larger fixed overhead cost, but O(1) insertion/removal and (I think?) amortised O(1) earliest-time query.

[avdgrinten]

Pairing heaps have a bad O(n) worst case (might be relevant for real-time applications).