//  Heap sort algorithm for n elements 
//  in a Monitored array, a.


#include <iostream.h>
#include "array.h"
#include "heaps.C"

extern MArray a;
void swap (int,int);
void heapify (int);

void heap (int n)
{  int i,j,k,lc,rc;
   int key;
// adjust (n);			// for paging heaps only
   heapify (n);

   k = n;
   k--;
   while (k>0)
     {  swap (k,0);
	key = a[i=0];
	j = 1;
	if (k>2 && a[2]>a[1]) j = 2;	// j is larger child of 0.
	while (j<k && a[j]>key)
	  {  a[i] = a[j];
	     i = j;
	     child (i,lc,rc);	// find left child and right child
	     j = lc;
	     if (rc<k && a[rc]>a[lc]) j = rc;	// larger child
	  }
	a[i] = key;
	k--;
      }
//   unadjust (n);		// paging heaps only
}

void heapify (int n)
//  convert an array into a heap
{  int i,j,k;
   int key;
   k = 1;
   while (k<n)
     {  i = k;
	key = a[k];
	j = parent (i);
	while (i>0 && key>a[j])
	  {  a[i] = a[j];
	     i = j;
             j = parent (i);
	     if (j<0) j = 0;
	  }
	a[i] = key;
	k++;
      }
}