SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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