Class Demo1

Tree/heap/Demo1.java:8–92

package heap;

public class Demo1 
{
	public static void buildHeap_TopDown(int[] a, int n)
    {
    	for(int i=2; i<=n; i++)
    		restoreUp(i,a);
    }
	
    public static void buildHeap_BottomUp(int[] a, int n)
    {
    	for(int i=n/2; i>=1; i--)
    		restoreDown(i,a,n);
    }
	
    private static void restoreUp(int i, int[] a)
    {
    	int k=a[i];  
    	int iparent=i/2;
    	
    	while(a[iparent]<k)      /* No sentinel : while(iparent>=1 && a[iparent]<k)  */
    	{
    		a[i]=a[iparent];
    		i=iparent;
    		iparent=i/2;
    	}
    	a[i]=k; 
    }
    
    private static void restoreDown(int i, int[] a, int n)
    {
    	int k=a[i];
    	int lchild=2*i, rchild=lchild+1;
    		
    	while(rchild<=n)
    	{
    		if( k>=a[lchild] && k>=a[rchild] )  
    		{
    			a[i]=k;
    			return;
    		}
    		else if(a[lchild] > a[rchild])
    		{
    			a[i]=a[lchild]; 
    			i=lchild;
    		}
    		else
    		{
    			a[i]=a[rchild];
    			i=rchild;
    		}
    		lchild=2*i;
    		rchild=lchild+1;
    	}

    	/*If number of nodes is even*/	
    	if(lchild==n && k<a[lchild]) 
    	{
    		a[i]=a[lchild];