BinomialHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <functional>
#include <utility>
 
#include <ogdf/basic/heap/HeapBase.h>
 
namespace ogdf {
 
 
template<typename T>
struct BinomialHeapNode {
    template<typename, typename> friend class BinomialHeap;
protected:
    T value; 
 
    size_t rank; 
 
    BinomialHeapNode<T> *parent; 
    BinomialHeapNode<T> *next; 
    BinomialHeapNode<T> *child; 
 
    explicit BinomialHeapNode(const T &nodeValue)
    : value(nodeValue),
      rank(0), parent(nullptr), next(nullptr), child(nullptr)
    {
    }
};
 
 
 
template<typename T, typename C = std::less<T>>
class BinomialHeap : public HeapBase<BinomialHeap<T, C>, BinomialHeapNode<T>, T, C>
{
 
    using base_type = HeapBase<BinomialHeap<T, C>, BinomialHeapNode<T>, T, C>;
 
public:
 
    explicit BinomialHeap(const C &cmp = C(), int initialSize = -1);
 
    virtual ~BinomialHeap();
 
    const T &top() const override;
 
    BinomialHeapNode<T> *push(const T &value) override;
 
    void pop() override;
 
    void decrease(BinomialHeapNode<T> *heapNode, const T &value) override;
 
    void merge(BinomialHeap<T, C> &other) override;
 
    const T &value(BinomialHeapNode<T> *heapNode) const override {
        return heapNode->value;
    }
 
private:
    BinomialHeapNode<T> *m_root; 
 
    BinomialHeapNode<T> *join(BinomialHeapNode<T> *a, BinomialHeapNode<T> *b);
    void merge(BinomialHeapNode<T> *other);
 
    static void link(BinomialHeapNode<T> *parent, BinomialHeapNode<T> *child);
 
    static void release(BinomialHeapNode<T> *heapNode);
};
 
 
template<typename T, typename C>
BinomialHeap<T, C>::BinomialHeap(const C &cmp, int /* unused parameter */)
: base_type(cmp), m_root(nullptr) {}
 
 
template<typename T, typename C>
BinomialHeap<T, C>::~BinomialHeap()
{
    release(m_root);
    m_root = nullptr;
}
 
 
template<typename T, typename C>
void BinomialHeap<T, C>::release(BinomialHeapNode<T> *heapNode)
{
    while(heapNode != nullptr) {
        release(heapNode->child);
 
        BinomialHeapNode<T> *next = heapNode->next;
        delete heapNode;
        heapNode = next;
    }
}
 
 
template<typename T, typename C>
inline const T &BinomialHeap<T, C>::top() const
{
    BinomialHeapNode<T> *min = m_root;
    for(BinomialHeapNode<T> *it = m_root->next; it != nullptr; it = it->next) {
        if(this->comparator()(it->value, min->value)) {
            min = it;
        }
    }
 
    return min->value;
}
 
 
template<typename T, typename C>
BinomialHeapNode<T> *BinomialHeap<T, C>::push(const T &value)
{
    BinomialHeapNode<T> *heapNode = new BinomialHeapNode<T>(value);
 
    merge(heapNode);
    return heapNode;
}
 
 
template<typename T, typename C>
void BinomialHeap<T, C>::pop()
{
    BinomialHeapNode<T> *curr = m_root, *min = m_root, *minPrev = nullptr;
 
    while(curr->next != nullptr) {
        if(this->comparator()(curr->next->value, min->value)) {
            min = curr->next;
            minPrev = curr;
        }
        curr = curr->next;
    }
 
    if(min == m_root) {
        m_root = min->next;
    } else {
        minPrev->next = min->next;
    }
 
    // Children list has to be reversed before it can be merged.
    BinomialHeapNode<T> *reversed = nullptr, *child = min->child;
    while(child != nullptr) {
        BinomialHeapNode<T> *next = child->next;
        child->next = reversed;
        reversed = child;
        child = next;
    }
    merge(reversed);
    delete min;
}
 
 
template<typename T, typename C>
void BinomialHeap<T, C>::decrease(BinomialHeapNode<T> *heapNode, const T &value)
{
    // BinomialHeap::decrease is not supported
    OGDF_ASSERT(false);
 
    heapNode->value = value;
 
    while(heapNode->parent != nullptr &&
          this->comparator()(heapNode->value, heapNode->parent->value))
    {
        std::swap(heapNode->value, heapNode->parent->value);
        heapNode = heapNode->parent;
    }
}
 
 
template<typename T, typename C>
void BinomialHeap<T, C>::merge(BinomialHeap<T, C> &other)
{
    merge(other.m_root);
    other.m_root = nullptr;
}
 
 
template<typename T, typename C>
inline BinomialHeapNode<T> *BinomialHeap<T, C>::join(
    BinomialHeapNode<T> *a, BinomialHeapNode<T> *b)
{
    if(a == nullptr) {
        return b;
    }
    if(b == nullptr) {
        return a;
    }
 
    if(b->rank < a->rank) {
        std::swap(a, b);
    }
 
    BinomialHeapNode<T> *head = a;
    while(b != nullptr) {
        if(a->next == nullptr) {
            a->next = b;
            break;
        }
 
        if(b->rank < a->next->rank) {
            BinomialHeapNode<T> *nextB = b->next;
            b->next = a->next;
            a->next = b;
 
            a = b;
            b = nextB;
        } else {
            a = a->next;
        }
    }
 
    return head;
}
 
 
template<typename T, typename C>
inline void BinomialHeap<T, C>::merge(BinomialHeapNode<T> *other)
{
    m_root = join(m_root, other);
    if(m_root == nullptr) {
        return;
    }
 
    BinomialHeapNode<T> *prev = nullptr, *curr = m_root, *next = m_root->next;
    while(next != nullptr) {
        if(curr->rank != next->rank || (next->next != nullptr &&
                                        next->next->rank == curr->rank))
        {
            prev = curr;
            curr = next;
            next = curr->next;
            continue;
        }
 
        if(this->comparator()(curr->value, next->value)) {
            curr->next = next->next;
            link(curr, next);
        } else if(prev == nullptr) {
            m_root = next;
            link(next, curr);
            curr = next;
        } else {
            prev->next = next;
            link(next, curr);
            curr = next;
        }
        next = curr->next;
    }
}
 
 
template<typename T, typename C>
inline void BinomialHeap<T, C>::link(
    BinomialHeapNode<T> *parent, BinomialHeapNode<T> *child)
{
    child->next = parent->child;
    child->parent = parent;
    parent->child = child;
    parent->rank++;
}
 
}