BinomialHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/heap/HeapBase.h>
 
#include <cstddef>
#include <functional>
 
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++;
}
 
}