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

Go to the documentation of this file.

#ifndef HEAPSET_H
#define HEAPSET_H

#include <list>
#include "stdinc.h"
#include "Util.h"

namespace grafalgo {

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

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

        // access methods
        index   findMin(int) const;
        uint64_t getKey(index) const;
        int     heapSize(int) const;

        // predicates 
        bool    empty(int);     

        // modifiers 
        bool    insert(index, uint64_t, int);
        index   deleteMin(int);
        void    changeKeyMin(uint64_t, int);

        string& toString(int, string&) const;
private:
        static const int d = 8;         
        int     maxHeap;                

        index   *heaps;                 
        uint64_t *key;                  

        int     *root;                  
        int     *bot;                   
        int     *hSize;                 
        
        int     *child;                 
        int     *parent;                
        int     *pred;                  
        
        int     free;                   

        index   nodeMinPos(int) const;  
        void    siftup(index,int);      
        void    siftdown(index,int);    
};

inline int HeapSet::nodeMinPos(int p) const {
        if (p == -1 || heaps[p] == 0) return -1;
        int minPos = p;
        for (int q = p+1; q < p+D && heaps[q] != 0; q++)
                if (key[heaps[q]] < key[heaps[minPos]])
                        minPos = q;
        return minPos;
}

// Return item at top of heap
inline int HeapSet::findMin(int h) const {
        if (hSize[h] == 0) return 0;
if (root[h] == -1)
cerr << "HeapSet::findMin: non-empty heap has root=-1\n";
        int p = nodeMinPos(root[h]);
if (p < 0) {
cerr << "HeapSet::findMin: nodeMinPos returned " << p
     << " h=" << h << " root[h]=" << root[h] << " heaps[" << root[h] << "]="
     << heaps[root[h]] << " hSize[h]=" << hSize[h] << endl;
}
        return (p < 0 ? 0 : heaps[p]);
}

// Return key of i.
inline uint64_t HeapSet::getKey(index i) const { return key[i]; }

// Return true if heap is empty, else false.
inline bool HeapSet::empty(int h) { return hSize[h] == 0; };

// Return the size of a heap.
inline int HeapSet::heapSize(int h) const { return hSize[h]; };

} // ends namespace

#endif