43 #define PQHEAP_MEM_DEBUG if(0) 54 static const int PAGESIZE = 1024;
71 static inline unsigned int heap_lchild(
unsigned int index) {
75 static inline unsigned int heap_rchild(
unsigned int index) {
80 static inline unsigned int heap_parent(
unsigned int index) {
86 static unsigned int mymin(
unsigned int a,
unsigned int b) {
112 unsigned int cur_elts;
115 unsigned int max_elts;
118 void heapify(
unsigned int root);
126 inline pqheap_t1(T* a,
unsigned int size);
133 unsigned int fill(T* a,
unsigned int size);
136 inline bool full(
void);
139 inline bool empty(
void);
146 inline unsigned int size(
void)
const {
return cur_elts; };
149 inline bool min(T& elt);
162 inline bool insert(
const T& elt);
172 void set(
long i, T& elt);
175 inline friend ostream& operator<<(ostream& s, const pqheap_t1<T> &pq) {
176 s <<
"PQ: "; s.flush();
177 for (
unsigned int i=0; i< mymin(10, pq.cur_elts); i++) {
194 inline void heapstatus(
int d);
195 inline void heaptouch(
unsigned int pos);
196 unsigned int *numtouch;
207 elements =
new T [
size];
208 cout <<
"pqheap_t1: register memory\n";
215 cerr <<
"could not allocate priority queue: insufficient memory..\n";
224 numtouch =
new unsigned int[size/PAGESIZE];
226 for(
int i=0; i<size/PAGESIZE; i++) {
243 cerr <<
"Using slow build in pqheap_t1" << endl;
253 for (
int i = heap_parent(max_elts-1); i>=0; i--) {
265 cout << endl <<
"pagesize = " << PAGESIZE << endl;
266 cout <<
"max_elts = " << max_elts << endl;
267 unsigned int n = max_elts / PAGESIZE;
268 for(
unsigned int i=0; i<n; i++) {
269 cout << form(
"PQTEMP %d\t%d", i, numtouch[i]) << endl;
290 for (i = 0; i<
size; i++) {
309 return cur_elts == max_elts;
316 return cur_elts == 0;
346 cerr <<
"unguarded min failed" << endl;
374 numtouch[pos/PAGESIZE]++;
375 assert(numtouch[pos/PAGESIZE] > 0);
382 static int count = 0;
383 static int delta = 0;
388 if((count % 10000) == 0) {
389 cout << endl << form(
"PQHEAP %d\t%d", cur_elts, delta) << endl;
406 elements[0] = elements[--cur_elts];
433 if ((!
min(next_elt)) ||
434 !(next_elt.getPriority() == elt.getPriority())) {
438 elt = elt + next_elt;
467 for (ii = cur_elts++;
468 ii && (elements[heap_parent(ii)].getPriority() > elt.getPriority());
469 ii = heap_parent(ii)) {
470 elements[ii] = elements[heap_parent(ii)];
487 unsigned int min_index = root;
488 unsigned int lc = heap_lchild(root);
489 unsigned int rc = heap_rchild(root);
500 if ((lc < cur_elts) &&
501 ((elements[lc].getPriority()) < elements[min_index].getPriority())) {
504 if ((rc < cur_elts) &&
505 ((elements[rc].getPriority()) < elements[min_index].getPriority())) {
509 if (min_index != root) {
510 T tmp_q = elements[min_index];
512 elements[min_index] = elements[root];
513 elements[root] = tmp_q;
539 for (
unsigned int i=0; i<cur_elts; i++) {
540 cout << elements[i].getPriority().field1() <<
",";
554 cout << a.getPriority().field1() <<
".." 555 << b.getPriority().field1();
557 cout <<
" (" << cur_elts <<
")]";
566 #endif // _PQUEUE_HEAP_H
unsigned int num_elts(void)
pqheap_t1(unsigned int size)
unsigned int size(void) const
void delete_min_and_insert(const T &x)
#define assert(condition)
bool extract_all_min(T &elt)
unsigned int fill(T *a, unsigned int size)
bool insert(const T &elt)