18 template <
class type,
class ptype>
25 inline const type& top()
const {
return h[1].x; }
26 inline const ptype& topPriority()
const {
return h[1].p; }
33 if(h.size()>1) heapifyDown(1);
36 void push(
const type& x,
const ptype& p)
42 heapifyUp((
int)h.size()-1);
45 int find(
const type& x)
const 47 for(
size_t i=1;i<h.size();i++)
48 if(h[i].x==x)
return (
int)i;
52 int findByPriority(
const type& x,
const ptype& p)
const 54 return findElement(1,x,p);
57 void adjust(
const type& x,
const ptype& p)
65 void _adjust(
int i,
const ptype& p)
67 assert(i>=1 && i<=size());
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; }
84 for(
int i=2;i<=size();i++)
85 if(h[parent(i)].p < h[i].p)
return false;
91 for(
int i=1;i<=size();i++) {
93 LOG4CXX_INFO(KrisLibrary::logger(),
"\n");
96 LOG4CXX_INFO(KrisLibrary::logger(),
"("<<h[i].x<<
","<<h[i].p<<
")"<<
" ");
98 LOG4CXX_INFO(KrisLibrary::logger(),
"\n");
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; }
113 void heapifyUp(
int i)
126 void heapifyDown(
int i)
130 int size = (int)h.size();
131 while(child1(i)<size) {
133 if(child+1<size && h[child+1].p > h[child].p)
135 if(it.p < h[child].p)
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);
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.