SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
priorityqueue.h
Go to the documentation of this file.
1 //
2 // priorityqueue.h
3 // glib-core
4 //
5 // Created by Peter Lofgren on 8/5/15.
6 // Copyright (c) 2015 infolab. All rights reserved.
7 //
8 
9 #ifndef snap_core_priorityqueue_h
10 #define snap_core_priorityqueue_h
11 
12 
13 //typedef TInt TVal;
14 
15 // A max priority queue which supports changing the priority of items.
16 // Uses a binary heap, so operations run in O(log(n)) time, where n is
17 // the number of items in the priority queue.
18 template <class TVal>
20 public:
22 
23  void Insert(const TVal& X, float Priority) {
25  IndexToVal.Add(X);
26  // Priorities.Add(-INFINITY);
27  Priorities.Add(INT_MIN);
28  SetPriority(X, Priority);
29  }
30 
31  void SetPriority(const TVal& X, float NewPriority) {
32  if (!ValToIndex.IsKey(X)) {
33  Insert(X, NewPriority);
34  } else {
35  int i = ValToIndex.GetDat(X);
36  if (NewPriority >= GetPriority(X)) {
37  Priorities[i] = NewPriority;
38  while (i > 0 && Priorities[i] > Priorities[Parent(i)]) {
39  Swap(i, Parent(i));
40  i = Parent(i);
41  }
42  } else {
43  Priorities[i] = NewPriority;
44  MaxHeapify(i);
45  }
46  }
47  }
48 
49  float GetPriority(const TVal& X) {
50  if (ValToIndex.IsKey(X)) {
51  return Priorities[ValToIndex.GetDat(X)];
52  } else {
53  return 0.0f; // Default value is 0.0
54  }
55  }
56 
57  float GetMaxPriority() {
58  IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
59  return Priorities[0];
60  }
61 
62  TVal PopMax() {
63  IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
64  TVal maxVal = IndexToVal[0];
65  Swap(0, Priorities.Len() - 1);
68  ValToIndex.DelKey(maxVal);
69 
70  MaxHeapify(0);
71  return maxVal;
72  }
73 
74  bool IsEmpty() {
75  return Size() == 0;
76  }
77 
78  int Size() {
79  return Priorities.Len();
80  }
81 
82  // Copies the current priorities into the given hash table
84  for (int i = 0; i < Priorities.Len(); i++) {
85  Result.AddDat(IndexToVal[i], Priorities[i]);
86  }
87  }
88 
89 private:
93 
94  int Parent(int i) { return (i + 1) / 2 - 1; }
95  int Left(int i) { return i * 2 + 1; }
96  int Right(int i) { return i * 2 + 2; }
97 
98  void Swap(int i, int j) {
99  Priorities.Swap(i, j);
100  IndexToVal.Swap(i, j);
101  ValToIndex.GetDat(IndexToVal[i]) = i;
102  ValToIndex.GetDat(IndexToVal[j]) = j;
103  }
104 
105  // If the max-heap invariant is satisfied except for index i possibly being smaller than a child, restore the invariant.
106  void MaxHeapify(int i) {
107  int largest = i;
108  if (Left(i) < Priorities.Len() && Priorities[Left(i)] > Priorities[largest]) {
109  largest = Left(i);
110  }
111  if (Right(i) < Priorities.Len() && Priorities[Right(i)] > Priorities[largest]) {
112  largest = Right(i);
113  }
114  if (largest != i) {
115  Swap(i, largest);
116  MaxHeapify(largest);
117  }
118  }
119 };
120 #endif
121 
122 /*
123  void Insert(const Tval& X, float Priority);
124  void SetPriority(const TVal& X, float NewPriority);
125  float GetPriority(const TVal& X);
126  float GetMaxPriority();
127  TVal PopMax();
128  bool IsEmpty();
129 */
#define IAssertR(Cond, Reason)
Definition: bd.h:265
float GetPriority(const TVal &X)
Definition: priorityqueue.h:49
void GetPriorities(THash< TVal, TFlt > &Result)
Definition: priorityqueue.h:83
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
void DelKey(const TKey &Key)
Definition: hash.h:404
void Swap(int i, int j)
Definition: priorityqueue.h:98
int Parent(int i)
Definition: priorityqueue.h:94
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
int Right(int i)
Definition: priorityqueue.h:96
void SetPriority(const TVal &X, float NewPriority)
Definition: priorityqueue.h:31
void MaxHeapify(int i)
Definition: hash.h:97
void Insert(const TVal &X, float Priority)
Definition: priorityqueue.h:23
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
float GetMaxPriority()
Definition: priorityqueue.h:57
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
TDat & AddDat(const TKey &Key)
Definition: hash.h:238