heap.cc

A C++ library which finds associations within sets of items, using a fast in-memory algorithm

#include <unistd.h>

#include "Trans.h"
#include "Heap.h"

Heap::Heap( int nn ) { nelts = 0; n = nn; h = new (Trans *)[nn+1]; };
Heap::Heap( Trans **p, int nn ) { nelts = n = nn; h = p ; /* also need to heapify */};

void Heap::heapify( int nn ) {
	for( int i = 0; i < nn; ) siftup(++i);
};

void Heap::ins( Trans * pt ) {
	h[++nelts] = pt;
	siftup(nelts);
};

Trans * Heap::peek() const { return( nelts > 0 ? h[1] : NULL ); };

void Heap::swapsert( Trans * &pt ) { // swap head and pt; sift down
	Trans * tmp;
	tmp = pt; pt = h[1]; h[1] = tmp;
	siftdown();
};

int Heap::tstswap( int i, int j ) {
	//nswap++;
	int tst = ( *h[i] < *h[j] );
	if( tst )
		{ Trans * tmp = h[i]; h[i]=h[j]; h[j]=tmp; };
	return tst;
};

void Heap::siftup(int m) {
	int i,j;
	for( i = m ; (j = i>>1) > 0 && tstswap(i,j); i = j );
};

void Heap::siftdown() {
	//nsift++;
        int j =1;
	while( (j = (2*j)) <= nelts ) {
		if( (j < nelts) &&  ( *h[j+1] < *h[j] )) j++;
		if( !tstswap( j, j>>1 ) )
			break;
	};
};

int Heap::chk() {
	int i;
	for( i = 2; ( i <= nelts ) && *h[ i/2 ] <= *h[i]; i++ );
	return( i <= nelts ? i : 0 );
	};

int Heap::nelt() const { return nelts; };

Trans * Heap::delmin() {
	Trans * min = NULL;
	if( nelts > 0 ) {
		nelts--;
		min = h[1];
		};
	if( nelts > 0 ) {
		h[1] = h[nelts+1];
		siftdown();
	};
	return min;
}
void Heap::prt() {
  int i;
  for( i=1; i<=nelts; i++ ) h[i]->prt(0);
}
void Heap::prt( int i ) { h[i]->prt(0); };