/Users/jst/src/grafalgo/cpp/include/DiffHeap.cpp

#ifndef DIFFHEAP_H
#define DIFFHEAP_H

#include "Adt.h"

namespace grafalgo {

typedef int keytyp;

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

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

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

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

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

        // stats methods
        void    clearStats();
        string& stats2string(string&) const;

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

        index   *h;                     
        int     *pos;                   
        keytyp  *dkey;                  

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

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

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

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

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

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

} // ends namespace

#endif