All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PrioQueueForInts.h
Go to the documentation of this file.
1 /*
2  * BucketPQ.h
3  *
4  * Created on: 26.06.2015
5  * Author: Henning
6  */
7 
8 #ifndef PRIOQUEUEFORINTS_H_
9 #define PRIOQUEUEFORINTS_H_
10 
11 #include "../auxiliary/Log.h"
12 #include <list>
13 #include <limits>
14 #include "../Globals.h"
15 
16 namespace Aux {
17 
18 typedef NetworKit::index index;
19 typedef NetworKit::count count;
20 typedef std::list<index> Bucket;
21 
28 private:
29  std::vector<Bucket> buckets; // the actual buckets
30  std::vector<Bucket::iterator> nodePtr; // keeps track of node positions
31  std::vector<index> myBucket; // keeps track of current bucket = priority
32  unsigned int minNotEmpty; // current min priority
33  int maxNotEmpty; // current max priority
34  index maxPrio; // maximum admissible priority
35  count numElems; // number of elements stored
36 
43  void insert(index elem, index prio);
44 
45 public:
54  PrioQueueForInts(std::vector<index>& prios, index maxPrio);
55 
59  ~PrioQueueForInts() = default;
60 
65  void remove(index elem);
66 
72  void changePrio(index elem, index prio);
73 
77  index extractMin();
78 
82  index extractMax();
83 
90  index extractAt(index prio);
91 
96  index priority(index elem);
97 
101  bool empty() const;
102 
106  count size() const;
107 };
108 
109 } /* namespace Aux */
110 #endif /* BUCKETPQ_H_ */
Addressable priority queue for elements in the range [0,n) and integer priorities in the range [0...
Definition: PrioQueueForInts.h:27
NetworKit::index index
Definition: BloomFilter.h:16
std::list< index > Bucket
Definition: BucketPQ.h:21
uint64_t index
Typedefs.
Definition: Globals.h:20
NetworKit::count count
Definition: BloomFilter.h:17
class deprecated("Use MaximalCliques instead.")]] MaxClique
Exact algorithm for computing the size of the largest clique in a graph.
Definition: MaxClique.h:24
uint64_t count
Definition: Globals.h:21