FibonacciHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/heap/HeapBase.h>
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <functional>
 
namespace ogdf {
 
 
template<typename T>
struct FibonacciHeapNode {
    template<typename, typename>
    friend class FibonacciHeap;
 
protected:
    T value; 
 
    size_t rank; 
    bool marked; 
 
    FibonacciHeapNode<T>* parent; 
    FibonacciHeapNode<T>* child; 
    FibonacciHeapNode<T>* prev; 
    FibonacciHeapNode<T>* next; 
 
    FibonacciHeapNode()
        : rank(0), marked(false), parent(nullptr), child(nullptr), prev(this), next(this) { }
 
    explicit FibonacciHeapNode(const T& nodeValue)
        : value(nodeValue)
        , rank(0)
        , marked(false)
        , parent(nullptr)
        , child(nullptr)
        , prev(this)
        , next(this) { }
};
 
 
template<typename T, typename C = std::less<T>>
class FibonacciHeap : public HeapBase<FibonacciHeap<T, C>, FibonacciHeapNode<T>, T, C> {
    using base_type = HeapBase<FibonacciHeap<T, C>, FibonacciHeapNode<T>, T, C>;
 
public:
    explicit FibonacciHeap(const C& cmp = C(), int initialSize = -1);
 
    virtual ~FibonacciHeap();
 
    const T& top() const override;
 
    FibonacciHeapNode<T>* push(const T& value) override;
 
    void pop() override;
 
    void decrease(FibonacciHeapNode<T>* heapNode, const T& value) override;
 
    void merge(FibonacciHeap<T, C>& other) override;
 
    const T& value(FibonacciHeapNode<T>* heapNode) const override { return heapNode->value; }
 
private:
    FibonacciHeapNode<T>* m_minimal;
    FibonacciHeapNode<T>* m_knot;
 
    std::array<FibonacciHeapNode<T>*, sizeof(size_t) * 8> m_ranked;
 
    void remove();
    void compress();
 
    void link(FibonacciHeapNode<T>* root, FibonacciHeapNode<T>* child);
    void detach(FibonacciHeapNode<T>* heapNode);
    void merge(FibonacciHeapNode<T>* other);
    void splice(FibonacciHeapNode<T>* target, FibonacciHeapNode<T>* heapNode);
    void restore(FibonacciHeapNode<T>* heapNode);
 
    void release(FibonacciHeapNode<T>* heapNode);
};
 
template<typename T, typename C>
FibonacciHeap<T, C>::FibonacciHeap(const C& cmp, int /* unused parameter */)
    : base_type(cmp), m_minimal(nullptr), m_knot(new FibonacciHeapNode<T>()) {
    m_ranked.fill(nullptr);
}
 
template<typename T, typename C>
FibonacciHeap<T, C>::~FibonacciHeap() {
    release(m_knot);
}
 
template<typename T, typename C>
void FibonacciHeap<T, C>::release(FibonacciHeapNode<T>* heapNode) {
    if (heapNode == nullptr) {
        return;
    }
 
    FibonacciHeapNode<T>* end = heapNode;
    do {
        release(heapNode->child);
 
        FibonacciHeapNode<T>* next = heapNode->next;
        delete heapNode;
        heapNode = next;
    } while (heapNode != end);
}
 
template<typename T, typename C>
inline const T& FibonacciHeap<T, C>::top() const {
    OGDF_ASSERT(m_minimal != nullptr);
    return m_minimal->value;
}
 
template<typename T, typename C>
FibonacciHeapNode<T>* FibonacciHeap<T, C>::push(const T& value) {
    FibonacciHeapNode<T>* heapNode = new FibonacciHeapNode<T>(value);
    splice(m_knot, heapNode);
 
    if (m_minimal == nullptr || this->comparator()(heapNode->value, m_minimal->value)) {
        m_minimal = heapNode;
    }
 
    return heapNode;
}
 
template<typename T, typename C>
void FibonacciHeap<T, C>::pop() {
    // Special case for tree with only one node.
    if (m_knot->next->next == m_knot && m_knot->next->child == nullptr) {
        m_knot->prev = m_knot->next = m_knot;
        delete m_minimal;
        m_minimal = nullptr;
        return;
    }
 
    remove();
    compress();
 
    // Find new minimal node in compressed tree list.
    m_minimal = m_knot->next;
    for (auto it = m_knot->next->next; it != m_knot; it = it->next) {
        if (this->comparator()(it->value, m_minimal->value)) {
            m_minimal = it;
        }
    }
}
 
template<typename T, typename C>
void FibonacciHeap<T, C>::decrease(FibonacciHeapNode<T>* heapNode, const T& value) {
    heapNode->value = value;
    if (this->comparator()(heapNode->value, m_minimal->value)) {
        m_minimal = heapNode;
    }
 
    restore(heapNode);
}
 
template<typename T, typename C>
void FibonacciHeap<T, C>::merge(FibonacciHeap<T, C>& other) {
    if (other.m_minimal == nullptr) {
        return;
    }
 
    FibonacciHeapNode<T>* next = other.m_knot->next;
    detach(other.m_knot);
    merge(next);
 
    if (this->comparator()(other.m_minimal->value, m_minimal->value)) {
        m_minimal = other.m_minimal;
    }
    other.m_minimal = nullptr;
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::remove() {
    if (m_minimal->child) {
        FibonacciHeapNode<T>* it = m_minimal->child;
        do {
            FibonacciHeapNode<T>* next = it->next;
            it->parent = nullptr;
            splice(m_knot, it);
 
            it = next;
        } while (it != m_minimal->child);
    }
    detach(m_minimal);
    delete m_minimal;
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::compress() {
    size_t maxr = 0;
 
    for (auto it = m_knot->next; it != m_knot;) {
        FibonacciHeapNode<T>* next = it->next;
 
        size_t r = it->rank;
        maxr = std::max(r, maxr);
        while (m_ranked[r]) {
            if (this->comparator()(m_ranked[r]->value, it->value)) {
                link(m_ranked[r], it);
                it = m_ranked[r];
            } else {
                link(it, m_ranked[r]);
            }
            m_ranked[r] = nullptr;
            r++;
            maxr = std::max(maxr, r);
        }
        m_ranked[r] = it;
 
        it = next;
    }
 
    for (size_t i = 0; i <= maxr; i++) {
        m_ranked[i] = nullptr;
    }
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::link(FibonacciHeapNode<T>* root, FibonacciHeapNode<T>* child) {
    child->marked = false;
    child->parent = root;
    root->rank++;
 
    if (root->child) {
        splice(root->child, child);
    } else {
        detach(child);
        root->child = child;
    }
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::detach(FibonacciHeapNode<T>* heapNode) {
    heapNode->prev->next = heapNode->next;
    heapNode->next->prev = heapNode->prev;
    heapNode->next = heapNode;
    heapNode->prev = heapNode;
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::merge(FibonacciHeapNode<T>* other) {
    m_knot->next->prev = other->prev;
    other->prev->next = m_knot->next;
    m_knot->next = other;
    other->prev = m_knot;
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::splice(FibonacciHeapNode<T>* target, FibonacciHeapNode<T>* heapNode) {
    detach(heapNode);
    target->next->prev = heapNode;
    heapNode->next = target->next;
    target->next = heapNode;
    heapNode->prev = target;
}
 
template<typename T, typename C>
inline void FibonacciHeap<T, C>::restore(FibonacciHeapNode<T>* heapNode) {
    for (;;) {
        FibonacciHeapNode<T>* parent = heapNode->parent;
        if (parent == nullptr) {
            return;
        }
 
        // We need to make sure parent has valid children after the splice.
        parent->rank--;
        if (parent->rank == 0) {
            parent->child = nullptr;
        } else if (parent->child == heapNode) {
            parent->child = heapNode->next;
        }
 
        heapNode->parent = nullptr;
        splice(m_knot, heapNode);
 
        // If parent is unmarked we can stop cut cascade.
        if (!parent->marked) {
            parent->marked = true;
            return;
        }
 
        heapNode = parent;
    }
}
 
}