KrisLibrary  1.0.0
Heap.h
1 #ifndef HEAP_H
2 #define HEAP_H
3 
4 #include <KrisLibrary/Logger.h>
5 #include <vector>
6 #include <assert.h>
7 using namespace std;
8 
18 template <class type,class ptype>
19 class Heap
20 {
21 public:
22  Heap() : h(1)
23  {}
24 
25  inline const type& top() const { return h[1].x; }
26  inline const ptype& topPriority() const { return h[1].p; }
27 
28  void pop()
29  {
30  assert(!empty());
31  h[1]=h.back();
32  h.resize(h.size()-1);
33  if(h.size()>1) heapifyDown(1);
34  }
35 
36  void push(const type& x,const ptype& p)
37  {
38  item it;
39  it.x=x;
40  it.p=p;
41  h.push_back(it);
42  heapifyUp((int)h.size()-1);
43  }
44 
45  int find(const type& x) const
46  {
47  for(size_t i=1;i<h.size();i++)
48  if(h[i].x==x) return (int)i;
49  return 0;
50  }
51 
52  int findByPriority(const type& x,const ptype& p) const
53  {
54  return findElement(1,x,p);
55  }
56 
57  void adjust(const type& x, const ptype& p)
58  {
59  int i=find(x);
60  if(i) _adjust(i,p);
61  else push(x,p);
62  }
63 
64  //NOTE: i must be an index in the array
65  void _adjust(int i,const ptype& p)
66  {
67  assert(i>=1 && i<=size());
68  if(h[i].p < p) { //increase
69  h[i].p=p;
70  heapifyUp(i);
71  }
72  else { //decrease
73  h[i].p=p;
74  heapifyDown(i);
75  }
76  }
77 
78  inline void clear() { h.resize(1); }
79  inline bool empty() const { return h.size()==1; }
80  inline int size() const { return (int)h.size()-1; }
81 
82  bool isHeap() const
83  {
84  for(int i=2;i<=size();i++)
85  if(h[parent(i)].p < h[i].p) return false;
86  return true;
87  }
88 
89  void print() const {
90  int level=1;
91  for(int i=1;i<=size();i++) {
92  if(i == (1<<level)) {
93  LOG4CXX_INFO(KrisLibrary::logger(),"\n");
94  level++;
95  }
96  LOG4CXX_INFO(KrisLibrary::logger(),"("<<h[i].x<<","<<h[i].p<<")"<<" ");
97  }
98  LOG4CXX_INFO(KrisLibrary::logger(),"\n");
99  }
100 
101 private:
102  struct item
103  {
104  type x;
105  ptype p;
106  };
107 
108  //assume 1-based array
109  inline int parent(int i) const { return i>>1; }
110  inline int child1(int i) const { return i<<1; }
111  inline int child2(int i) const { return (i<<1)+1; }
112 
113  void heapifyUp(int i)
114  {
115  item it=h[i];
116  while(i>1) {
117  int par=parent(i);
118  if(it.p>h[par].p)
119  h[i]=h[par];
120  else break;
121  i=par;
122  }
123  h[i]=it;
124  }
125 
126  void heapifyDown(int i)
127  {
128  item it=h[i];
129  int child;
130  int size = (int)h.size();
131  while(child1(i)<size) {
132  child = child1(i);
133  if(child+1<size && h[child+1].p > h[child].p)
134  child++;
135  if(it.p < h[child].p)
136  h[i]=h[child];
137  else break;
138  i=child;
139  }
140  h[i]=it;
141  }
142 
143  int findElement(int i,const type& x,const ptype& p) const {
144  if(p > h[i].p) return 0;
145  if(p == h[i].p && x == h[i].x) return i;
146  int res=findElement(child1(i),x,p);
147  if(res != 0) return res;
148  res=findElement(child2(i),x,p);
149  return res;
150  }
151 
152  vector<item> h;
153 };
154 
155 
156 #endif
Implements a heap that stores objects of type type, with priority keys of type ptype.
Definition: Heap.h:19
Definition: rayprimitives.h:132
The logging system used in KrisLibrary.