heapify

heap.c

#include <stdlib.h>
#include <stdio.h>

int *lots;  		//parking lots
#define LOTSMAX 16		//lots size

void Heapify (int i, int mx);
void car_enter ();
void car_leave (int i);
void print_lots ();

int
main ()
{
  int i;
  lots = (int *) calloc ((LOTSMAX), sizeof (int));
  printf ("car enter\n");
  for (i = 0; i < LOTSMAX; ++i)
    {
      if (lots[0] != 1)
	{
	  car_enter ();
	  print_lots ();
	}
    }
  printf ("car leave\n");
  for (i = LOTSMAX - 1; i >= 0; --i)
    {
      if (lots[i] != 0)
	{
	  car_leave (i);
	  print_lots ();
	}
    }
  free (lots);
  return 1;
}

void
print_lots ()
{
  int i;
  for (i = 0; i < LOTSMAX; ++i)
    {
      printf ("%d ", lots[i]);
    }
  printf ("\n");
}

void
Heapify (int i, int mx)
{
  int l, r, min, parent;
//heapify downward
  l = 2 * i + 1;
  r = 2 * i + 2;
  min = i;
  if (lots[min] > lots[l] && l <= mx)
    min = l;
  if (lots[min] > lots[r] && r <= mx)
    min = r;
  if (min != i)
    {
      int tmp = lots[i];
      lots[i] = lots[min];
      lots[min] = tmp;
      i = min;
      Heapify (i, mx);
    }
//heapify upward
  parent = (i - 1) / 2;
  if (parent < 0)
    return;
  if (lots[parent] > lots[i])
    {
      int tmp = lots[i];
      lots[i] = lots[parent];
      lots[parent] = tmp;
      i = parent;
      Heapify (i, mx);
    }
}
void
car_enter ()
{
  lots[0] = 1;			// 1 is occupied
  Heapify (0, (LOTSMAX - 1));
}

void
car_leave (int i)
{
  lots[i] = 0;			// 0 is empty
  Heapify (i, (LOTSMAX - 1));
}