// Binary heap routines - root has minimum
// Heap must have a handle array such that handle[i]
// gives the heap subscript for id number i.  In addition,
// there is a parallel array "id" to "priority" that gives
// the id number for priority[i] (thus, handle[id[i]]==i . . .).

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>

#define LEFT(x) (2*(x))
#define RIGHT(x) (2*(x)+1)
#define PARENT(x) ((x)/2)

float CPUtime()
{
  struct rusage rusage;
  getrusage(RUSAGE_SELF,&rusage);
  return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
    + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void buildMinHeap(int priority[],int id[],int handle[])
{
int n=priority[0];
int i,iPriority,iId,j,best,l,r;

for (i=n/2;i>0;i--)
{
  iPriority=priority[i];
  iId=id[i];
  j=i;
  while (1)
  {
    l=LEFT(j);
    if (l>n)
      break;
    r=RIGHT(j);
    if (r>n || priority[l]<priority[r])
      best=l;
    else
      best=r;
    if (iPriority<=priority[best])
      break;
    priority[j]=priority[best];
    id[j]=id[best];
    handle[id[j]]=j;
    j=best;
  }
  priority[j]=iPriority;
  id[j]=iId;
  handle[id[j]]=j;
}
}

void changePriority(int iId,int iPriority,int priority[],int id[],int handle[])
{
int n=priority[0];
int i=handle[iId],j,best,l,r,p;

if (iPriority>priority[i])
{
  j=i;
  while (1)
  {
    l=LEFT(j);
    if (l>n)
      break;
    r=RIGHT(j);
    if (r>n || priority[l]<priority[r])
      best=l;
    else
      best=r;
    if (iPriority<=priority[best])
      break;
    priority[j]=priority[best];
    id[j]=id[best];
    handle[id[j]]=j;
    j=best;
  }
  priority[j]=iPriority;
  id[j]=iId;
  handle[id[j]]=j;
  return;
}

j=i;
while (1)
{
  p=PARENT(j);
  if (p<1 || priority[p]<=iPriority)
    break;
  priority[j]=priority[p];
  id[j]=id[p];
  handle[id[j]]=j;
  j=p;
}
priority[j]=iPriority;
id[j]=iId;
handle[id[j]]=j;
}

void insertHeap(int iId,int iPriority,int priority[],int id[],int handle[])
{
int j,best,p;

j=(++priority[0]);
while (1)
{
  p=PARENT(j);
  if (p<1 || priority[p]<=iPriority)
    break;
  priority[j]=priority[p];
  id[j]=id[p];
  handle[id[j]]=j;
  j=p;
}
priority[j]=iPriority;
id[j]=iId;
handle[id[j]]=j;
}

void extractHeap(int priority[],int id[],int handle[],
  int *oId,int *oPriority)
{
int n;
int i,iPriority,iId,j,best,l,r;

(*oId)=id[1];
(*oPriority)=priority[1];
handle[id[1]]=(-1); // Invalidate handle

priority[0]--;
n=priority[0];
if (n==0)
  return;
iPriority=priority[n+1];
iId=id[n+1];
j=1;
while (1)
{
  l=LEFT(j);
  if (l>n)
    break;
  r=RIGHT(j);
  if (r>n || priority[l]<priority[r])
    best=l;
  else
    best=r;
  if (iPriority<=priority[best])
    break;
  priority[j]=priority[best];
  id[j]=id[best];
  handle[id[j]]=j;
  j=best;
}
priority[j]=iPriority;
id[j]=iId;
handle[id[j]]=j;
}

void dumpTables(int priority[],int id[],int handle[],int maxHandle)
{
int i;

printf("Have %d items\n",priority[0]);
printf("  i  handle   id  priority\n");
for (i=0;i<=maxHandle;i++)
  if (i==0 || i>priority[0])
  {
    if (i!=25)
      printf(" %3d  %3d\n",i,handle[i]);
  }
  else if (i==maxHandle)
    printf(" %3d         %3d    %3d\n",i,id[i],priority[i]);
  else
    printf(" %3d  %3d    %3d    %3d\n",i,handle[i],id[i],priority[i]);
for (i=2;i<=priority[0];i++)
  if (priority[i]<priority[PARENT(i)])
    printf("HEAP PROPERTY ERROR at %d\n",i);
}

int priority[4000001],id[4000001],handle[4000000];

main()
{
int i,j;
int oId,oPriority;
float startCPU;

srandom(666);
priority[0]=2000000;
for (i=0;i<2000000;i++)
{
  priority[i+1]=abs(random())%20000;
  id[i+1]=i;
  handle[i]=i+1;
}
//printf("Before build\n");
//dumpTables(priority,id,handle,25);
startCPU=CPUtime();
buildMinHeap(priority,id,handle);
printf("buildMinHeap time %f\n",CPUtime()-startCPU);
//printf("After build\n");
//dumpTables(priority,id,handle,25);
startCPU=CPUtime();
for (i=2000000;i<=3999999;i++)
{
  j=abs(random())%20000;
  //printf("insert item %d with priority %d\n",i,j);
  insertHeap(i,j,priority,id,handle);
  //dumpTables(priority,id,handle,i+1);
}
printf("insertHeap time %f\n",CPUtime()-startCPU);
startCPU=CPUtime();
for (i=0;i<4000000;i++)
{
  j=abs(random())%20000;
  //printf("change priority on %d to %d\n",i,j);
  changePriority(i,j,priority,id,handle);
  //dumpTables(priority,id,handle,50);
}
printf("changePriority time %f\n",CPUtime()-startCPU);
startCPU=CPUtime();
for (i=0;i<4000000;i++)
{
/*
  if (i%100000==0)
    printf("Extract of %d took %f\n",i,CPUtime()-startCPU);
*/
  extractHeap(priority,id,handle,&oId,&oPriority);
  //printf("extract heap returned id %d and priority %d\n",oId,oPriority);
  //dumpTables(priority,id,handle,50);
}
printf("extractHeap time %f\n",CPUtime()-startCPU);
}