/Users/jst/src/grafalgo/cpp/include/Dheap.h

Go to the documentation of this file.

#ifndef DHEAP_H
#define DHEAP_H

//#include "stdinc.h"
#include "Adt.h"

namespace grafalgo {

typedef int keytyp;

class Dheap : public Adt {
public:         Dheap(int,int);
                ~Dheap();

        // common methods
        void    clear();
        void    resize(int);
        void    expand(int);
        void    copyFrom(const Dheap&);

        // access methods
        index   findmin() const;
        keytyp  key(index) const;

        // predicates
        bool    member(index) const;
        bool    empty() const;  
        int     size() const;

        // modifiers
        void    insert(index,keytyp);
        void    remove(index);
        index   deletemin();
        void    changekey(index,keytyp);        

        string& toString(string&) const;
private:
        int     d;                      
        int     hn;                     

        index   *h;                     
        int     *pos;                   
        keytyp  *kee;                   

        index   minchild(index);                
        void    siftup(index,int);
        void    siftdown(index,int);

        void    makeSpace(int);
        void    freeSpace();
};

inline int Dheap::findmin() const { return hn == 0 ? 0 : h[1]; }

inline int Dheap::deletemin() {
        if (hn == 0) return 0;
        index i = h[1]; remove(h[1]);
        return i;
}

inline keytyp Dheap::key(index i) const { return kee[i]; }

inline bool Dheap::member(index i) const { return pos[i] != 0; }

inline bool Dheap::empty() const { return hn == 0; };

inline int Dheap::size() const { return hn; };

} // ends namespace

#endif