a simple Priority Queue implementation in C++

main.cpp

#include <iostream>

#include "pqueue.hpp"

int main() {
  PriorityQueue<int*> q{};

  for (int i=0; i < 12; i++) {
    std::printf("%d, first\n", i);
    q.push(i, new int{i});

    std::printf("%d, second\n", i);
    q.push(i, new int{i*i});
  }

  for (int i=0; i < 12; i++) {
    auto first = q.pop_top().value();
    auto second = q.pop_bottom().value();

    std::printf("%d, first: %d\n", i, *first);
    std::printf("%d, second: %d\n", i, *second);

    delete first;
    delete second;
  }

  std::printf("testing copy assignment\n");
  auto q2 = q;

  std::printf("testing move assignment\n");
  auto q3 = std::move(q2);

  std::printf("testing std::initializer\n");
  auto q4 = PriorityQueue<int> { {1, 1}, {2, 2}, {3, 3} };

  return 0;
}

pqueue.hpp

#ifndef PQUEUE_H_
#define PQUEUE_H_

#include <queue>
#include <utility>
#include <optional>
#include <initializer_list>

template<class T, class PT = int>
struct PriorityNode final {
  PT priority;

  PriorityNode* prev;
  PriorityNode* next;
  std::queue<T> q;

  PriorityNode(T data, PT priority)
    : priority(priority)
    , prev(nullptr)
    , next(nullptr)
    , q(std::queue<T>{})
    {
      q.push(data);
    }
};

template<class T, class PT = int>
class PriorityQueue final {
  PriorityNode<T, PT>* top_;
  PriorityNode<T, PT>* bottom_;

 public:
  PriorityQueue()
    : top_(nullptr)
    , bottom_(nullptr)
    {}

  PriorityQueue(std::initializer_list<std::pair<PT, T>> lst) {
    top_ = nullptr;
    bottom_ = nullptr;

    for (auto [priority, item] : lst)
      push(priority, item);
  }

  PriorityQueue(const PriorityQueue& other);
  
  PriorityQueue(PriorityQueue&& other) noexcept
    : top_(std::exchange(other.top_, nullptr))
    , bottom_(std::exchange(other.bottom_, nullptr))
    {}

  PriorityQueue& operator=(const PriorityQueue& other) {
    return *this = PriorityQueue(other);
  }

  PriorityQueue& operator=(PriorityQueue&& other) noexcept {
    if (this == &other)
      return *this;

    std::swap(top_, other.top_);
    std::swap(bottom_, other.bottom_);

    return *this;
  }

  ~PriorityQueue();

  bool empty() const { return top_ == nullptr; }

  std::optional<T> top() const
  {
    return top_ ? top_->q.front() : std::nullopt;
  }
  std::optional<T> bottom() const
  {
    return bottom_ ? bottom_->q.front() : std::nullopt;
  }

  void push(PT priority, T item) { _push(priority, item); }
  void push(PT priority, std::queue<T> q);

  std::optional<T> pop_top();
  std::optional<T> pop_bottom();

  std::optional<T> pull_highest_priority_item()
    { return pop_top(); }

  std::optional<T> pull_lowest_priority_item()
    { return pop_bottom(); }

  void insert_item_with_priority(PT priority, T item)
  {
    push(priority, item);
  }

 private:
  PriorityNode<T, PT>* _push(PT priority, T item);
};

template<class T, class PT>
PriorityQueue<T, PT>::PriorityQueue(const PriorityQueue& other)
{
  if (this == &other) return;

  top_ = nullptr;
  bottom_ = nullptr;

  PriorityQueue<T, PT> q{};

  for (auto node = other.bottom_; node; node = node->prev)
    q.push(node->priority, node->q);

  *this = std::move(q);
}

template<class T, class PT>
PriorityQueue<T, PT>::~PriorityQueue() {
  if (!top_) return;

  auto head = top_, next = top_->next;
  for (
    /* void */;
    next;
    head = next, next = next->next
  ) { delete head; }

  // last node
  delete head;
}

template<class T, class PT>
void PriorityQueue<T, PT>::push(PT priority, std::queue<T> q)
{
  auto node = _push(priority, q.front());
  q.pop();

  while (!q.empty()) {
    node->q.push(q.front());
    q.pop();
  }
}

template<class T, class PT>
PriorityNode<T, PT>*
PriorityQueue<T, PT>::_push(PT priority, T item)
{
  if (!top_) {
    top_ = new PriorityNode<T, PT>(item, priority);
    bottom_ = top_;

    return top_;
  }

  if (priority > top_->priority) {
    auto head = new PriorityNode<T, PT>(item, priority);

    top_->prev = head;
    head->next = top_;
    top_ = head;

    return head;
  }

  // find a head node which its next is either nullptr
  // or has a priority less than given `priority`
  auto head = top_, next = top_->next;
  for (
    /* void */;
    next && priority < next->priority;
    head = next, next = next->next
  );

  // if has same priority, goes into bucket
  if (next && next->priority == priority) {
    next->q.push(item);

    return next;
  }

  // insert the node between head and next
  auto node = new PriorityNode<T, PT> { item, priority };
  node->prev = head;
  node->next = next;

  head->next = node;
  if (next) {
    next->prev = node;
  } else { // head was bottom, now node is.
    bottom_ = node;
  }

  return node;
}

template<class T, class PT>
std::optional<T> PriorityQueue<T, PT>::pop_top()
{
  if (!top_)
    return std::nullopt;

  T temp = top_->q.front();
  top_->q.pop();

  if (top_->q.empty()) {
    auto next = top_->next;
    delete top_;
    top_ = next;
    if (top_)
      top_->prev = nullptr;
  }

  if (!top_)
    bottom_ = nullptr;

  return temp;
}

template<class T, class PT>
std::optional<T> PriorityQueue<T, PT>::pop_bottom()
{
  if (!bottom_)
    return std::nullopt;

  T temp = bottom_->q.front();
  bottom_->q.pop();

  if (bottom_->q.empty()) {
    auto prev = bottom_->prev;
    delete bottom_;
    bottom_ = prev;
    if (bottom_)
      bottom_->next = nullptr;
  }

  if (!bottom_)
    top_ = nullptr;

  return temp;
}

#endif  /* PQUEUE_H_ */