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


#include <iostream.h>
#include "array.h"
#include "pheaps.C"		// for paging heaps

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

void pheap (int n)
{  int i,j,k,lc,rc;
   int key;
   int left, right;		// Control order of operand evaluation
   adjust (n);			// for paging heaps only
   heapify (n);

   k = n;
   decr (k);			// k--;
   while (k>0)
     {  swap (k,0);		// swap (0,k) generates more faults
	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)
		{ left = a[lc];	// finding left first generates fewer faults
	          right = a[rc];
	     	  // left = a[lc];
	     	  if (right>left) 	// a[lc]<a[rc]
			j = rc;			// larger child
		}
	  }
	a[i] = key;
	decr (k);		// k-- for ordinary heaps
      }
   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;
	incr (k);		// k++ for ordinary heaps
      }
}