RMHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/heap/HeapBase.h>
 
#include <functional>
#include <random>
 
namespace ogdf {
 
 
template<typename T>
struct RMHeapNode {
    template<typename, typename>
    friend class RMHeap;
 
protected:
    T value; 
 
    RMHeapNode<T>* parent; 
    RMHeapNode<T>* left; 
    RMHeapNode<T>* right; 
 
    explicit RMHeapNode(const T& nodeValue)
        : value(nodeValue), parent(nullptr), left(nullptr), right(nullptr) { }
};
 
 
template<typename T, typename C = std::less<T>>
class RMHeap : public HeapBase<RMHeap<T, C>, RMHeapNode<T>, T, C> {
    using base_type = HeapBase<RMHeap<T, C>, RMHeapNode<T>, T, C>;
 
public:
    explicit RMHeap(const C& cmp = C(), int initialSize = -1);
 
    virtual ~RMHeap();
 
    const T& top() const override;
 
    RMHeapNode<T>* push(const T& value) override;
 
    void pop() override;
 
    void decrease(RMHeapNode<T>* heapNode, const T& value) override;
 
    void merge(RMHeap<T, C>& other) override;
 
    const T& value(RMHeapNode<T>* heapNode) const override { return heapNode->value; }
 
private:
    std::default_random_engine m_rand; 
    RMHeapNode<T>* m_root; 
 
    RMHeapNode<T>* merge(RMHeapNode<T>* a, RMHeapNode<T>* b);
    void remove(RMHeapNode<T>* heapNode);
 
    static void release(RMHeapNode<T>* heapNode);
};
 
template<typename T, typename C>
RMHeap<T, C>::RMHeap(const C& cmp, int initialSize)
    : base_type(cmp), m_rand((std::random_device())()), m_root(nullptr) { }
 
template<typename T, typename C>
RMHeap<T, C>::~RMHeap() {
    release(m_root);
}
 
template<typename T, typename C>
const T& RMHeap<T, C>::top() const {
    return m_root->value;
}
 
template<typename T, typename C>
RMHeapNode<T>* RMHeap<T, C>::push(const T& value) {
    RMHeapNode<T>* heapNode = new RMHeapNode<T>(value);
    m_root = merge(m_root, heapNode);
 
    return heapNode;
}
 
template<typename T, typename C>
void RMHeap<T, C>::pop() {
    RMHeapNode<T>* root = m_root;
    m_root = merge(m_root->left, m_root->right);
    if (m_root != nullptr) {
        m_root->parent = nullptr;
    }
    delete root;
}
 
template<typename T, typename C>
void RMHeap<T, C>::decrease(RMHeapNode<T>* heapNode, const T& value) {
    heapNode->value = value;
    if (heapNode == m_root) {
        return;
    }
 
    remove(heapNode);
    heapNode->left = nullptr;
    heapNode->right = nullptr;
    heapNode->parent = nullptr;
 
    m_root = merge(m_root, heapNode);
}
 
template<typename T, typename C>
void RMHeap<T, C>::merge(RMHeap<T, C>& other) {
    m_root = merge(m_root, other.m_root);
    other.m_root = nullptr;
}
 
template<typename T, typename C>
RMHeapNode<T>* RMHeap<T, C>::merge(RMHeapNode<T>* a, RMHeapNode<T>* b) {
    if (a == nullptr) {
        return b;
    }
    if (b == nullptr) {
        return a;
    }
 
    if (this->comparator()(a->value, b->value)) {
        if (m_rand() % 2 == 0) {
            a->left = merge(a->left, b);
            if (a->left != nullptr) {
                a->left->parent = a;
            }
        } else {
            a->right = merge(a->right, b);
            if (a->right != nullptr) {
                a->right->parent = a;
            }
        }
        return a;
    } else {
        if (m_rand() % 2 == 0) {
            b->left = merge(b->left, a);
            if (b->left != nullptr) {
                b->left->parent = b;
            }
        } else {
            b->right = merge(b->right, a);
            if (b->right != nullptr) {
                b->right->parent = b;
            }
        }
        return b;
    }
}
 
template<typename T, typename C>
void RMHeap<T, C>::remove(RMHeapNode<T>* heapNode) {
    RMHeapNode<T>* merged = merge(heapNode->left, heapNode->right);
    if (heapNode == heapNode->parent->left) {
        heapNode->parent->left = merged;
    } else {
        heapNode->parent->right = merged;
    }
    if (merged != nullptr) {
        merged->parent = heapNode->parent;
    }
}
 
template<typename T, typename C>
void RMHeap<T, C>::release(RMHeapNode<T>* heapNode) {
    if (heapNode == nullptr) {
        return;
    }
 
    release(heapNode->left);
    release(heapNode->right);
    delete heapNode;
}
 
}