81 #define MY_LOG_DEBUG_ID(x) //inhibit debug printing 102 sprintf(str,
"BasicMinMaxHeap: allocate %ld\n",
103 (
long)((size+1)*
sizeof(T)));
128 void insert(
const T& elt);
130 bool min(T& elt)
const ;
132 bool max(T& elt)
const;
146 friend ostream& operator<<(ostream& s, const BasicMinMaxHeap<T> &pq) {
149 for(i = 1; i <= pq.size(); i++) {
150 s <<
" " << pq.get(i);
157 virtual void grow()=0;
160 long log2(
long n)
const;
161 int isOnMaxLevel(
HeapIndex i)
const {
return (log2(i) % 2); };
162 int isOnMinLevel(
HeapIndex i)
const {
return !isOnMaxLevel(i); };
166 int hasRightChild(
HeapIndex i)
const {
return (rightChild(i) <=
size()); };
170 int hasChildren(
HeapIndex i)
const {
return (2*i) <=
size(); };
247 if(hasRightChild(i) && (leftChildValue(i) > rightChildValue(i))) {
248 return rightChild(i);
259 if(hasRightChild(i) && (leftChildValue(i) < rightChildValue(i))) {
260 return rightChild(i);
278 q = smallestChild(p);
279 if(
A[p] >
A[q]) p = q;
284 if(hasRightChild(i,&p)) {
287 q = smallestChild(p);
288 if(
A[p] >
A[q]) p = q;
291 if(
A[p] <
A[minpos]) minpos = p;
308 if(
A[p] <
A[q]) p = q;
313 if(hasRightChild(i,&p)) {
317 if(
A[p] <
A[q]) p = q;
320 if(
A[p] >
A[maxpos]) maxpos = p;
342 if (!hasChildren(i)) {
346 m = smallestChildGrandchild(i);
347 if(isGrandchildOf(i, m)) {
350 if(
A[m] >
A[parent(m)]) {
376 if(!hasChildren(i)) {
381 m = largestChildGrandchild(i);
382 if(isGrandchildOf(i, m)) {
385 if(
A[m] <
A[parent(m)]) {
408 if(isOnMinLevel(i)) {
421 if(isOnMinLevel(i)) {
422 if (m && (
A[i] >
A[m])) {
429 if (m && (
A[i] <
A[m])) {
445 while (m && (
A[i] <
A[m])) {
462 while(m && (
A[i] >
A[m])) {
476 ostrstream *ostr =
new ostrstream();
479 for(i=1; i<=
size(); i++) {
480 *ostr <<
" " <<
A[i];
481 if(ostr->pcount() > 70) {
482 cout << ostr->str() << endl;
484 ostr =
new ostrstream();
485 *ostr <<
"[" << i <<
"]";
488 cout << ostr->str() << endl;
498 for (
unsigned int i=1; i<=
size(); i++) {
499 cout <<
A[i].getPriority() <<
",";
512 cout << a.getPriority() <<
".." 515 cout <<
" (" <<
size() <<
")]";
531 XXX cerr <<
"insert: " << elt << endl;
567 if ((!
min(next_elt)) ||
568 !(next_elt.getPriority() == elt.getPriority())) {
572 elt = elt + next_elt;
659 p = (T*)LargeMemory::alloc(
sizeof(T) * (n+1));
698 XXX cerr << i <<
": " << val << endl;
699 if(val.getPriority() < prev.getPriority()) {
701 cerr <<
"n=" << n << endl;
702 cerr <<
"val=" << val << endl;
703 cerr <<
"prev=" << prev << endl;
704 cerr <<
"looks like minmaxheap.min is broken!!" << endl;
751 virtual void grow() { fprintf(stderr,
"MinMaxHeap::grow: not implemented\n");
assert(0); exit(1); };
763 for (i = 0; !
full() && i<n; i++) {
776 #define MMHEAP_INITIAL_SIZE 1024
MinMaxHeap(HeapIndex size)
#define MMHEAP_INITIAL_SIZE
static T * allocateHeap(HeapIndex n)
BasicMinMaxHeap(HeapIndex size)
void insert(const T &elt)
UnboundedMinMaxHeap(HeapIndex size)
static void freeHeap(T *)
#define assert(condition)
#define MY_LOG_DEBUG_ID(x)
virtual ~BasicMinMaxHeap(void)
bool extract_all_min(T &elt)
virtual ~UnboundedMinMaxHeap()
HeapIndex fill(T *arr, HeapIndex n)
HeapIndex get_maxsize() const