1 #ifndef FIXED_SIZE_HEAP_H 2 #define FIXED_SIZE_HEAP_H 7 #include <KrisLibrary/errors.h> 12 template <
class ptype>
17 :objectToHeapIndex(maxValue),h(1)
19 for(
int i=0;i<maxValue;i++)
20 objectToHeapIndex[i]=0;
21 h.reserve(maxValue+1);
29 void init(
int maxValue)
31 objectToHeapIndex.resize(maxValue);
32 std::fill(objectToHeapIndex.begin(),objectToHeapIndex.end(),0);
34 h.reserve(maxValue+1);
37 void increaseCapacity(
int maxValue)
39 objectToHeapIndex.resize(maxValue,0);
40 h.reserve(maxValue+1);
43 inline int top()
const {
return h[1].x; }
45 inline ptype topPriority()
const {
return h[1].p; }
47 inline ptype priority(
int item)
const {
return h[objectToHeapIndex[item]].p; }
52 objectToHeapIndex[h[1].x]=0;
55 if(h.size()>1) heapifyDown(1);
58 void push(
int x,
const ptype& p)
60 Assert(objectToHeapIndex[x]==0);
61 objectToHeapIndex[x] = (int)h.size();
66 heapifyUp((
int)h.size()-1);
69 int find(
const int x)
const 71 Assert(x >= 0 && x < (
int)objectToHeapIndex.size());
72 return objectToHeapIndex[x];
76 void adjust(
const int x,
const ptype& p)
79 if(i) adjustByHeapIndex(i,p);
83 void adjustByHeapIndex(
int i,
const ptype& p)
85 Assert(i>=1 && i<=size());
96 inline void clear() { h.resize(1); std::fill(objectToHeapIndex.begin(),objectToHeapIndex.end(),0); }
97 inline bool empty()
const {
return h.size()==1; }
98 inline int size()
const {
return (
int)h.size()-1; }
99 inline int maxObjects()
const {
return (
int)objectToHeapIndex.size(); }
103 for(
size_t i=1;i<h.size();i++)
104 Assert(objectToHeapIndex[h[i].x] == (
int)i);
105 for(
size_t i=0;i<objectToHeapIndex.size();i++)
106 if(objectToHeapIndex[i]!=0)
107 Assert(h[objectToHeapIndex[i]].x == i);
109 for(
int i=2;i<=size();i++)
110 if(h[parent(i)].p < h[i].p)
return false;
116 for(
int i=1;i<=size();i++) {
117 if(i == (1<<level)) {
118 LOG4CXX_INFO(KrisLibrary::logger(),
"\n");
121 LOG4CXX_INFO(KrisLibrary::logger(),
"("<<h[i].x<<
","<<h[i].p<<
")"<<
" ");
123 LOG4CXX_INFO(KrisLibrary::logger(),
"\n");
134 inline int parent(
int i)
const {
return i>>1; }
135 inline int child1(
int i)
const {
return i<<1; }
136 inline int child2(
int i)
const {
return (i<<1)+1; }
138 void heapifyUp(
int i)
145 objectToHeapIndex[h[i].x]=i;
151 objectToHeapIndex[h[i].x]=i;
154 void heapifyDown(
int i)
158 int size = (int)h.size();
159 while(child1(i)<size) {
161 if(child+1<size && h[child+1].p > h[child].p)
163 if(it.p < h[child].p) {
165 objectToHeapIndex[h[i].x]=i;
171 objectToHeapIndex[h[i].x]=i;
175 std::vector<int> objectToHeapIndex;
A heap of fixed maximum size N. Each element is indexed by an integer 0...N-1. The priority key of ea...
Definition: FixedSizeHeap.h:13
The logging system used in KrisLibrary.