tpl_fibonacci_heap.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef TPL_FIBONACCI_HEAP_H
# define TPL_FIBONACCI_HEAP_H
 
# include <ah-concepts.H>
# include <ahUtils.H>
# include <ah-errors.H>
# include <ahFunctional.H>
# include <vector>
# include <algorithm>
# include <utility>
 
namespace Aleph
{
  template <typename T, class Compare = Aleph::less<T>>
    requires StrictWeakOrder<Compare, T>
  class Fibonacci_Heap
  {
  public:
    struct Node
    {
      T data;               
      Node *parent = nullptr; 
      Node *child = nullptr;  
      Node *left = this;      
      Node *right = this;     
      size_t degree = 0;      
      bool mark = false;      
 
      explicit Node(const T & d) : data(d) {}
 
      explicit Node(T && d) noexcept(std::is_nothrow_move_constructible_v<T>)
        : data(std::move(d)) {}
 
      template <typename Arg, typename... Args>
        requires ((sizeof...(Args) >= 1) or
                  (not std::is_same_v<std::decay_t<Arg>, T> and
                   not std::is_same_v<std::decay_t<Arg>, Node>))
      explicit Node(Arg&& arg, Args&&... args)
        : data(std::forward<Arg>(arg), std::forward<Args>(args)...) {}
    };
 
  private:
    static constexpr size_t MAX_DEGREE = 128;
 
    Node *min_node = nullptr;  
    size_t num_nodes = 0;      
    Compare cmp;               
 
    std::vector<Node *> consolidate_array_;
 
    static void link(Node *y, Node *x)
    {
      // Remove y from root list
      y->left->right = y->right;
      y->right->left = y->left;
 
      // Make y a child of x
      y->parent = x;
      if (x->child == nullptr)
        {
          x->child = y;
          y->right = y;
          y->left = y;
        }
      else
        {
          y->left = x->child;
          y->right = x->child->right;
          x->child->right->left = y;
          x->child->right = y;
        }
 
      ++x->degree;
      y->mark = false;
    }
 
    void consolidate()
    {
      if (min_node == nullptr)
        return;
 
      // Use member vector to avoid repeated allocations
      if (consolidate_array_.size() < MAX_DEGREE)
        consolidate_array_.resize(MAX_DEGREE, nullptr);
      else
        std::fill(consolidate_array_.begin(), consolidate_array_.end(), nullptr);
 
      // Collect all root nodes to iterate safely while modifying links
      std::vector<Node *> root_nodes;
      Node *curr = min_node;
      do
        {
          root_nodes.push_back(curr);
          curr = curr->right;
        }
      while (curr != min_node);
 
      for (Node *w : root_nodes)
        {
          Node *x = w;
          size_t d = x->degree;
 
          while (d < MAX_DEGREE && consolidate_array_[d] != nullptr)
            {
              Node *y = consolidate_array_[d];
              // Ensure x has the smaller key (maintains heap property)
              if (cmp(y->data, x->data))
                std::swap(x, y);
 
              link(y, x);
              consolidate_array_[d] = nullptr;
              ++d;
            }
 
          if (d < MAX_DEGREE)
            consolidate_array_[d] = x;
        }
 
      // Reconstruct root list and find new minimum
      min_node = nullptr;
      for (size_t i = 0; i < MAX_DEGREE; ++i)
        {
          if (consolidate_array_[i] != nullptr)
            {
              consolidate_array_[i]->parent = nullptr;
              if (min_node == nullptr)
                {
                  min_node = consolidate_array_[i];
                  min_node->left = min_node;
                  min_node->right = min_node;
                }
              else
                {
                  // Insert into root list
                  consolidate_array_[i]->left = min_node;
                  consolidate_array_[i]->right = min_node->right;
                  min_node->right->left = consolidate_array_[i];
                  min_node->right = consolidate_array_[i];
 
                  if (cmp(consolidate_array_[i]->data, min_node->data))
                    min_node = consolidate_array_[i];
                }
            }
        }
    }
 
    void cut(Node *x, Node *y)
    {
      // Remove x from the child list of y
      if (x->right == x)
        y->child = nullptr;
      else
        {
          x->left->right = x->right;
          x->right->left = x->left;
          if (y->child == x)
            y->child = x->right;
        }
      --y->degree;
 
      // Add x to the root list
      x->left = min_node;
      x->right = min_node->right;
      min_node->right->left = x;
      min_node->right = x;
      x->parent = nullptr;
      x->mark = false;
    }
 
    void cascading_cut(Node *y)
    {
      while (y != nullptr)
        {
          Node *z = y->parent;
          if (z == nullptr)
            break;
 
          if (not y->mark)
            {
              y->mark = true;
              break;
            }
          cut(y, z);
          y = z;  // Continue with parent (iterative instead of recursive)
        }
    }
 
    void delete_all_nodes(Node *node)
    {
      if (node == nullptr)
        return;
 
      // Break the circular list to avoid use-after-free when checking
      // loop termination condition against a deleted node
      node->left->right = nullptr;
 
      Node *curr = node;
      while (curr != nullptr)
        {
          Node *next = curr->right;
          // Recursively delete children
          if (curr->child != nullptr)
            delete_all_nodes(curr->child);
          delete curr;
          curr = next;
        }
    }
 
    void add_to_root_list(Node *node)
    {
      node->parent = nullptr;
      if (min_node == nullptr)
        {
          min_node = node;
          node->left = node;
          node->right = node;
        }
      else
        {
          node->left = min_node;
          node->right = min_node->right;
          min_node->right->left = node;
          min_node->right = node;
 
          if (cmp(node->data, min_node->data))
            min_node = node;
        }
    }
 
  public:
    using value_type = T;
 
    using key_compare = Compare;
 
    using handle_type = Node *;
 
    explicit Fibonacci_Heap(Compare compare = Compare()) noexcept
      : cmp(compare)
    {
      consolidate_array_.reserve(MAX_DEGREE);
    }
 
    template <typename... Args>
    explicit Fibonacci_Heap(std::in_place_t, Args&&... args) noexcept
      : cmp(std::forward<Args>(args)...)
    {
      consolidate_array_.reserve(MAX_DEGREE);
    }
 
    ~Fibonacci_Heap()
    {
      clear();
    }
 
    Fibonacci_Heap(const Fibonacci_Heap &) = delete;
 
    Fibonacci_Heap &operator=(const Fibonacci_Heap &) = delete;
 
    Fibonacci_Heap(Fibonacci_Heap && other) noexcept
      : min_node(other.min_node),
        num_nodes(other.num_nodes),
        cmp(std::move(other.cmp)),
        consolidate_array_(std::move(other.consolidate_array_))
    {
      other.min_node = nullptr;
      other.num_nodes = 0;
    }
 
    Fibonacci_Heap &operator=(Fibonacci_Heap && other) noexcept
    {
      if (this != &other)
        {
          clear();
          min_node = other.min_node;
          num_nodes = other.num_nodes;
          cmp = std::move(other.cmp);
          consolidate_array_ = std::move(other.consolidate_array_);
          other.min_node = nullptr;
          other.num_nodes = 0;
        }
      return *this;
    }
 
    void swap(Fibonacci_Heap & other) noexcept
    {
      std::swap(min_node, other.min_node);
      std::swap(num_nodes, other.num_nodes);
      std::swap(cmp, other.cmp);
      std::swap(consolidate_array_, other.consolidate_array_);
    }
 
    [[nodiscard]] Node * insert(const T & val)
    {
      Node *node = new Node(val);
      add_to_root_list(node);
      ++num_nodes;
      return node;
    }
 
    [[nodiscard]]Node * insert(T && val)
    {
      Node *node = new Node(std::move(val));
      add_to_root_list(node);
      ++num_nodes;
      return node;
    }
 
    template <typename... Args>
    [[nodiscard]] Node * emplace(Args&&... args)
    {
      Node *node = new Node(std::forward<Args>(args)...);
      add_to_root_list(node);
      ++num_nodes;
      return node;
    }
 
    [[nodiscard]] const T & get_min() const
    {
      ah_underflow_error_if(is_empty()) << "Fibonacci_Heap::get_min: heap is empty";
      return min_node->data;
    }
 
    [[nodiscard]] Node * get_min_node() const noexcept
    {
      return min_node;
    }
 
    T extract_min()
    {
      ah_underflow_error_if(is_empty()) << "Fibonacci_Heap::extract_min: heap is empty";
 
      Node *z = min_node;
 
      // Add all children of z to the root list
      if (z->child != nullptr)
        {
          // First, set all children's parent to nullptr
          Node *child = z->child;
          do
            {
              child->parent = nullptr;
              child = child->right;
            }
          while (child != z->child);
 
          // Splice the child list into the root list
          Node *child_left = z->child->left;
          Node *z_right = z->right;
 
          z->right = z->child;
          z->child->left = z;
          child_left->right = z_right;
          z_right->left = child_left;
 
          z->child = nullptr;
        }
 
      // Remove z from root list
      if (z == z->right)
        {
          // z was the only root
          min_node = nullptr;
        }
      else
        {
          z->left->right = z->right;
          z->right->left = z->left;
          min_node = z->right;
          consolidate();
        }
 
      --num_nodes;
      T data = std::move(z->data);
      delete z;
      return data;
    }
 
    void decrease_key(Node *x, const T & k)
    {
      ah_invalid_argument_if(x == nullptr)
        << "Fibonacci_Heap::decrease_key: null node pointer";
      ah_domain_error_if(cmp(x->data, k))
        << "Fibonacci_Heap::decrease_key: new key is greater than current key";
 
      x->data = k;
      Node *y = x->parent;
 
      if (y != nullptr && cmp(x->data, y->data))
        {
          cut(x, y);
          cascading_cut(y);
        }
 
      if (cmp(x->data, min_node->data))
        min_node = x;
    }
 
    void decrease_key(Node *x, T && k)
    {
      ah_invalid_argument_if(x == nullptr)
        << "Fibonacci_Heap::decrease_key: null node pointer";
      ah_domain_error_if(cmp(x->data, k))
        << "Fibonacci_Heap::decrease_key: new key is greater than current key";
 
      x->data = std::move(k);
      Node *y = x->parent;
 
      if (y != nullptr && cmp(x->data, y->data))
        {
          cut(x, y);
          cascading_cut(y);
        }
 
      if (cmp(x->data, min_node->data))
        min_node = x;
    }
 
    [[nodiscard]] Node * update_key(Node *x, const T & k)
    {
      ah_invalid_argument_if(x == nullptr)
        << "Fibonacci_Heap::update_key: null node pointer";
 
      if (cmp(k, x->data))
        {
          // New key is smaller, use decrease_key
          decrease_key(x, k);
          return x;
        }
      if (cmp(x->data, k))
        {
          // New key is larger, delete and reinsert
          delete_node(x);
          return insert(k);
        }
      // Keys are equal, do nothing
      return x;
    }
 
    void delete_node(Node *x)
    {
      ah_invalid_argument_if(x == nullptr)
        << "Fibonacci_Heap::delete_node: null node pointer";
 
      // Step 1: If x is not a root, cut it and perform cascading cuts
      if (x->parent != nullptr)
        {
          Node *parent = x->parent;  // Save parent BEFORE cut
          cut(x, parent);
          cascading_cut(parent);     // Use saved parent
        }
 
      // Step 2: Make x the minimum (by temporarily pointing min_node to it)
      min_node = x;
 
      // Step 3: Extract x (which is now the "minimum")
      // We need to do extract_min logic but without returning data
      if (x->child != nullptr)
        {
          Node *child = x->child;
          do
            {
              child->parent = nullptr;
              child = child->right;
            }
          while (child != x->child);
 
          // Splice children into root list
          Node *child_left = x->child->left;
          Node *x_right = x->right;
 
          if (x == x->right)
            {
              // x was alone, children become the root list
              min_node = x->child;
            }
          else
            {
              x->right = x->child;
              x->child->left = x;
              child_left->right = x_right;
              x_right->left = child_left;
            }
        }
 
      // Remove x from root list
      if (x == x->right)
        {
          // x was alone in root list
          if (min_node == x)
            min_node = nullptr;  // x had no children either
          else
            consolidate();  // x had children, need to find true minimum
        }
      else
        {
          x->left->right = x->right;
          x->right->left = x->left;
          if (min_node == x)
            min_node = x->right;
          consolidate();
        }
 
      --num_nodes;
      delete x;
    }
 
    void merge(Fibonacci_Heap & other)
    {
      if (&other == this || other.is_empty())
        return;
 
      if (is_empty())
        {
          min_node = other.min_node;
          num_nodes = other.num_nodes;
        }
      else
        {
          // Concatenate root lists
          Node *this_right = min_node->right;
          Node *other_left = other.min_node->left;
 
          min_node->right = other.min_node;
          other.min_node->left = min_node;
          other_left->right = this_right;
          this_right->left = other_left;
 
          // Update minimum if necessary
          if (cmp(other.min_node->data, min_node->data))
            min_node = other.min_node;
 
          num_nodes += other.num_nodes;
        }
 
      // Clear the other heap (nodes now belong to us)
      other.min_node = nullptr;
      other.num_nodes = 0;
    }
 
    void merge(Fibonacci_Heap && other)
    {
      merge(other);
    }
 
    [[nodiscard]] bool is_empty() const noexcept
    {
      return min_node == nullptr;
    }
 
    [[nodiscard]] size_t size() const noexcept
    {
      return num_nodes;
    }
 
    void clear() noexcept(std::is_nothrow_destructible_v<T>)
    {
      if (min_node != nullptr)
        {
          delete_all_nodes(min_node);
          min_node = nullptr;
          num_nodes = 0;
        }
    }
 
    [[nodiscard]] bool empty() const noexcept
    {
      return is_empty();
    }
 
    void pop()
    {
      extract_min();
    }
 
    [[nodiscard]] const T & top() const
    {
      return get_min();
    }
 
    [[nodiscard]] Compare key_comp() const
    {
      return cmp;
    }
  };
 
  template <typename T, class Compare>
  void swap(Fibonacci_Heap<T, Compare> & a, Fibonacci_Heap<T, Compare> & b) noexcept
  {
    a.swap(b);
  }
 
} // namespace Aleph
 
# endif // TPL_FIBONACCI_HEAP_H