#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/****Copyright (c) 2002 All rights reserved
 ****A. V. Gerbessiotis and C. J. Siniolakis
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/

void maxheapify(char *keys,int n,int size,int (*compare)(),int l,int r)
{
	register int i,j;
	char	*x;

	x = (char *) malloc(size*sizeof(char));
	i=l;j=2*i+1;

	memcpy(x,&keys[i*size],size);

	while ( j <= r)
	{
		if (j < r) 
		{
			if (compare(&keys[(j)*size],&keys[(j+1)*size]) < 0)
			{
				j++;
			}
		}
		if (compare(x,&keys[(j)*size]) >= 0)
			break;

	memcpy(&keys[(i)*size],&keys[(j)*size],size);
	i=j;j=2*i+1;
	}
	memcpy(&keys[(i)*size],x,size);
}
	

void mxheapg(char *keys, int n, int size, int (*compare) ())
{
	register int l,r;
	char	*x;

	l = n/2+1; r=n-1;
	x = (char *) malloc(size*sizeof(char));

	while (l > 0)
	{
		l--;
		maxheapify(keys,n,size,compare,l,r);
	}
	while (r > 0)
	{
		memcpy(x,&keys[0],size);
		memcpy(&keys[0],&keys[(r)*size],size);
		memcpy(&keys[(r)*size],x,size);
		r--;
		maxheapify(keys,n,size,compare,l,r);
	}

}
