The heap structure on n nodes is the binary tree with nodes 0,1,...,n-1 such that the parent of each node j other than 0 is the floor of (j-1)/2 (and such that 0 is the root of the tree).

Warning: A number of books use a different convention. There, the nodes of the heap structure are 1,2,...,n, the parent of each node j other than 1 is the floor of j/2, and 1 is the root.

Now consider the following two problems:

1. Given an array a[0],a[1],...,a[n-1] of records and an index inc such that
   the array arises from a max-heap by increasing the value of a[inc].key,
   permute the n records so that the resulting array is again a max-heap;
   
2. Given an array a[0],a[1],...,a[n-1] of records and an index dec such that
   the array arises from a max-heap by decreasing the value of a[dec].key,
   permute the n records so that the resulting array is again a max-heap.

void bubbleup(record a[], int n, int vacant, record missing)
{
  int parent=(vacant-1)/2;

  while(vacant>0)
    {
      /* the actual value of a[vacant] is irrelevant;
         if   a[vacant] were overwritten with missing, 
	 then the max-heap condition would be satisfied 
	      everywhere except possibly at j=vacant */
          
      if(cmp(&a[parent],&missing)<0)
	{
	  a[vacant]=a[parent], vacant=parent, parent=(vacant-1)/2;
	}
      else
	break;
    }
  a[vacant]=missing;
}


void siftdown(record a[], int n, int vacant, record missing)
{
  int child=2*(vacant+1);

  while(child<n)
    {
      /* the actual value of a[vacant] is irrelevant;
         if   a[vacant] were overwritten with missing, 
	 then the max-heap condition would be satisfied 
	      everywhere except possibly at i=vacant */
          
      if(cmp(&a[child],&a[child-1])<0) 
	child--;
      if(cmp(&a[child],&missing)>0)
        {
          a[vacant]=a[child], vacant=child, child=2*(vacant+1);
        }
      else
	break;
    }

  if((child==n) && cmp(&a[n-1],&missing)>0)
    {
      a[vacant]=a[n-1], vacant=n-1;
    }

  a[vacant]=missing;
}

The version of Heapsort designed by Williams uses bubbleup and siftdown as follows:

void makeheap(record a[], int n)
{
  int k;
  
  for(k=1; k<n; k++) 
    bubbleup(a, n, k, a[k]);
}

void hsort(record a[], int n)
{
  int k;
  record temp;

  makeheap(a,n);

  for(k=n-1; k>0; k--) 
    {
      /* now a[0],a[1],    ...,a[k] is a heap and 
             a[k+1],a[k+2],...,a[n] is sorted      */

      temp=a[k], a[k]=a[0];
      siftdown(a, k, 0, temp);
    }
}

Here is the "accelerated Heapsort" that stems from Floyd's second improvement:

void hsort(record a[], int n)
{
  int k, drop, last;
  record temp;

  makeheap(a,n);

  drop = floor_of_lg(n-1, &last);
  for(k=n-1; k>0; k--) 
    {
      temp=a[k], a[k]=a[0];
      siftdown(a, k, 0, temp, drop);
      if (k==last)
	{
	  drop--, last/=2;
	}
    }
}

void makeheap(record a[], int n)
{
  int k, drop, first;
  
  drop=1, first=n/2-1;
  for(k=first; k>=0; k--)
    { 
      if(k==(first-1)/2)
	{
	  drop++, first=k;
	}
      siftdown(a, n, k, a[k], drop);
    }
}

void siftdown(record a[], int n, int vacant, record missing, int drop)
{
  int memo=vacant;
  int child, parent;
  int count, next_peek;

  count=0, next_peek=(drop+1)/2;

  child=2*(vacant+1);
  while(child<n)
    {
      if(cmp(&a[child],&a[child-1])<0)
        child--;
      a[vacant]=a[child], vacant=child, child=2*(vacant+1);

      count++;
      if (count==next_peek)
	{
	  if(cmp(&a[(vacant-1)/2],&missing)<=0)
	    break;
	  else
	    next_peek=(count+drop+1)/2;	      
	}
    }

  if(child==n)
    {
      a[vacant]=a[n-1], vacant=n-1;
    }
  
  parent=(vacant-1)/2;
  while(vacant>memo)    
    {
      if(cmp(&a[parent],&missing)<0)        
	{
          a[vacant]=a[parent], vacant=parent, parent=(vacant-1)/2;
	}
      else        
	break;
    }
  a[vacant]=missing;
}


int floor_of_lg(int n, int* power)
{
  /***********************************************************
  *  computes the largest power of 2 that is at most n and   *
  *  returns  the exponent in this power:                    *
  *            n =   1   2   3   4   5   6   7   8   9  ...  *
  *        power =   1   2   2   4   4   4   4   8   8  ...  *
  *   exponent k =   0   1   1   2   2   2   2   3   3  ...  *
  ***********************************************************/

  int k=0;
  for(*power=1; 2*(*power)<=n; (*power)*=2)
    k+=1;
  return k;
}