Heaps.h

Go to the documentation of this file.

#ifndef HEAPS_H
#define HEAPS_H

#include <stdio.h>
#include <limits.h>

// Poznamky:
// - Rozsahlejsi porovnani hald je v souboru Heaps_info_CZ.doc
// - Plati, ze v rodici je ulozena mensi hodnota nez v detech (nebo si jsou
//      hodnoty rovny).
//      (existuji i implementace, ktere pracuji obracene)
// - Pri ruseni haldy se nedealokuji prvky.
// - Funkce hald Merge a Union vymazou uzly v druhe halde
//      ( - presunou je do te, ktera zbude).
// - Uzivatel nesmi pouzit INT_MIN nebo nizsi pro hodnotu key
//      v kteremkoliv uzlu (je to specialni hodnota
//      pouzita ve funkcich Delete jako "zaporne nekonecno")

class GenericHeapNode;

// _NodeClass musi byt odvozena z GenericHeapNode
template <class _NodeClass, class _keyType>
class GenericHeap {
public:

    class GenericHeapNode {
    public:
        _keyType key;
    };

    virtual void Insert (_NodeClass *node) = 0;
    virtual _NodeClass* ExtractMin (void) = 0;
    virtual void DecreaseKey (_NodeClass *node, _keyType value) = 0;
    virtual _NodeClass* GetMin (void) = 0;
        // Tato funkce se od ExtractMin lisi tim, z
        // prvek z haldy nevymaze
    virtual _NodeClass* Delete (_NodeClass *node) = 0;
        // POZOR - Navratova hodnota nemusi byt stejna,
        // jako vstupni

    virtual bool IsEmpty() = 0;

protected:
};



class BinomialHeapNode;

// _NodeClass musi byt odvozena z BinomialHeapNode
template <class _NodeClass, class _keyType>
class BinomialHeap : public GenericHeap<_NodeClass, _keyType> {
public:

    class BinomialHeapNode : public GenericHeapNode {
    public:
        BinomialHeapNode *parent;
        BinomialHeapNode *child;
        BinomialHeapNode *sibling;
        int degree;

        virtual void Swap (void *node);
            // prohodi obsah tohoto uzlu se specifikovanym
            // (obsah se tady rovna [key]; parent, child, sibling
            // a degree musi zustat na miste)
    };

    BinomialHeap (void);
    ~BinomialHeap (void);

    virtual void Insert (_NodeClass *node);
    virtual _NodeClass* ExtractMin (void);
    virtual void DecreaseKey (_NodeClass *node, _keyType value);
        // snizi hodnotu klice na hodnotu [value]
    virtual _NodeClass* GetMin (void);
    virtual _NodeClass* Delete (_NodeClass *node);
    
    virtual void Union (BinomialHeap<_NodeClass, _keyType> *heap);

    virtual void FreeAllNodes();

    virtual bool IsEmpty() { return (head == NULL); }

protected:
    _NodeClass *head;

    inline void Link (_NodeClass *root1, _NodeClass *root2) {
        // Pripoji prvni strom "pod" druhy
        root1->parent = root2;
        root1->sibling = root2->child;
        root2->child = root1;
        root2->degree++;
    }
    void Merge (BinomialHeap<_NodeClass, _keyType> *heap);
        // Spoji dve haldy tak, aby stromy byly vysledne setrideny
        // podle velikosti.

    void FreeNodeSimple(_NodeClass *node);
        // Uvolni z pameti uzel a jeho potomky
};


template <class _NodeClass, class _keyType>
void BinomialHeap<_NodeClass, _keyType>::BinomialHeapNode::Swap (void *node)
{
    _keyType tmp = ((BinomialHeap::BinomialHeapNode*)node)->key;
    ((BinomialHeap::BinomialHeapNode*)node)->key = key;
    key = tmp;
}


// _NodeClass musi byt odvozena z FibonacciHeapNode
template <class _NodeClass, class _keyType>
class FibonacciHeap : public GenericHeap<_NodeClass, _keyType> {
public:
    class FibonacciHeapNode : public GenericHeapNode {
    public:
        FibonacciHeapNode *parent;
        FibonacciHeapNode *left;
        FibonacciHeapNode *right;
        FibonacciHeapNode *child;

        int degree : ((sizeof(int) * 8) - 1);
        unsigned int mark : 1;
        // nebo jenom:
    //   int degree;
    //   bool mark;
    };

    FibonacciHeap (void);
    ~FibonacciHeap (void);

    virtual void Insert (_NodeClass *node);
    virtual _NodeClass* ExtractMin (void);
    virtual void DecreaseKey (_NodeClass *node, _keyType value);
    virtual _NodeClass* GetMin (void);
    virtual _NodeClass* Delete (_NodeClass *node);
    
    virtual void Union (FibonacciHeap<_NodeClass, _keyType> *heap);

    virtual void FreeAllNodes();

    virtual bool IsEmpty() { return (head == NULL); }

protected:
    _NodeClass *head;
    _NodeClass *min;

    void Consolidate (void);
    void Link (_NodeClass *child, _NodeClass *parent);
    virtual void Cut (_NodeClass *node1, _NodeClass *node2);
    virtual void CascadingCut (_NodeClass *node);

    void FreeNodeSimple(_NodeClass *node);
        // Uvolni z pameti uzel a jeho potomky
};


// _NodeClass musi byt odvozena z ThinHeapNode
template <class _NodeClass, class _keyType>
class ThinHeap : public GenericHeap<_NodeClass, _keyType> {
public:

    class ThinHeapNode : public GenericHeapNode {
    public:
        ThinHeapNode *pl;
            // ukazatel na leveho sourozence nebo na otce
            // (v pripade nejlevejsiho sourozence)
            // V pripade seznamu korenu je v prvnim korenu
            // ukazatel na posledni a opacne (cyklicky spojovy seznam)
        ThinHeapNode *right;
        ThinHeapNode *child;

        int rank;
            // Viz popis struktury "thin heap".
            // POZOR - moje modifikace: Koren zde ma ulozeno
            // "[skutecny rank] - INT_MIN". Porovnanim proti
            // nule se da lehce poznat, ze je to koren
    };

    ThinHeap (void);

    virtual void Insert (_NodeClass *node);
    virtual _NodeClass* ExtractMin (void);
    virtual void DecreaseKey (_NodeClass *node, _keyType value);
    virtual _NodeClass* GetMin (void);
    virtual _NodeClass* Delete (_NodeClass *node);

    virtual void Union (ThinHeap<_NodeClass, _keyType> *heap);

    virtual bool IsEmpty() { return (head == NULL); }

protected:
    _NodeClass *head;
    _NodeClass *min;

    void Consolidate (void);
    void Link (_NodeClass *child, _NodeClass *parent);

    virtual void RepairViolations (_NodeClass *node);
};


#include "Heaps.cpp"

#endif