//本程序取自王曉東等著“算法設計與分析”第 130 頁，例4.7
//基于最小堆的貪心算法解多機調度問題
 //heapsort on minheap
 import java.io.*;
class MinHeap 
   {                      //Min-heap impmentation
     static jobNode[] Heap;  //Pointer to the heap array
     static int size;     //Maximum size of the heap
     static int n;        //Number of intents now in heapheapsoet
    public MinHeap(jobNode[] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}
    public int heapsize()//return current size of the heap
     {  return n;}
    public static boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 
    public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}
    public static int key( int [] q,int p)
     {  return q[p];}
  //return position for left child of pos
    public static int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }
  //return position for right child of pos
    public static int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }
    public static int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }
    public static  void buildheap() //Heapify contents of Heap
     {  for(int i=n/2-1;i>=0;i--)siftdown(i);}

    public static void swap(jobNode[] q,int i,int j)
     {      
       jobNode temp;
       temp=q[i];q[i]=q[j];q[j]=temp;}

    private static void siftdown(int pos) //put intent in itscorrent place
     {Assert_notFalse((pos>=0) && (pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if(j<(n-1)&&Heap[j].key()>Heap[j+1].key())
         j++;// j is now index of child with greater value
       if(Heap[pos].key()<=Heap[j].key()) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }
    public static void insert(jobNode val) //Insert value into heap
     {
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start t end of heap
     //Now sift up until curr's parent's key<curr's key
     while(curr!=0 && Heap[curr].key()<Heap[parent(curr)].key())
       {
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
       }
     }
    public static jobNode removemin()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     }
  //Remove intent at specified position 
    public static jobNode remove(int pos)
     {
      Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
      swap(Heap,pos,--n);//swap with last value
      if(n!=0)     //Not on last intent
      siftdown(pos);//put new heap root val in corrent place
      return Heap[n];
     }
   public static void outMinHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i].time+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemin()+"  ");
     System.out.println( );    //removemin places min value at end of heap
    } 
 }// class MinHeap
   class jobNode implements Comparable
  {
    int id;
    int time;
     jobNode(int i,int tt)
       {
         id=i;
         time=tt;
       }
     public int compareTo(Object x)
       {
        int xt=((jobNode)x).time;
        if(time<xt)return -1;
        if(time==xt)return 0;
        return 1;
       }
     public  int key()
     {  return time;}
  }
 class MachineNode implements Comparable
   { 
     static int id,avail;
     MachineNode(int i,int a)
     {
      id=i;
      avail=a;
     }
     public int compareTo(Object x)
     {
      int xa=((MachineNode)x).avail;
      if(avail<xa)return -1;
      if(avail==xa)return 0;
      return 1;
     }
      public static int key()
     {  return avail;}
   }
  public class Fac4_7_2
 {
    public static void mergeSort(jobNode[] a,int left,int right)
   {
     jobNode []b=new jobNode[a.length];
     if(left<right){
     int i=(left+right)/2;
     mergeSort(a,left,i);
     mergeSort(a,i+1,right);   
     merge(a,b,left,i,right);
     copy(a,b,left,right);
       }
    } 
   public static void copy(jobNode[] a,jobNode[] b,int i,int j)
    {
      
      for(int k=i;k<=j;k++)
      a[k]=b[k];
     } 
   public static void merge(jobNode [] c,jobNode [] d,int l,int m,int r)
     {//合并c[l:m]和c[m+1:r]到d[l:m]
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if(c[i].time-c[j].time>0)
             d[k++]=c[i++];
          else d[k++]=c[j++];
          if(i>m)
          for(int q=j;q<=r;q++)
              d[k++]=c[q];
          else 
           for(int q=i;q<=m;q++)
              d[k++]=c[q];
      }    
  public static void main(String args[])
   { 
     int m1=0,m=3;
     int a[]={2,14,4,16,6,5,3};
     int n1=a.length-1; 
       jobNode []d=new jobNode[n1+1];
     for(int i=0;i<=n1;i++)
      d[i]=new jobNode(i,a[i]);
      mergeSort(d,m1,n1); 
     //for(int i=0;i<=n1;i++)
     // System.out.println(d[i].time+"  ");
     MinHeap abc=new MinHeap(d,m1,3);    
     for(int i=m1;i<m;i++)
       {
         jobNode x1=d[i];
         abc.insert(x1);       
       }
     System.out.println("初始堆");
     abc.outMinHeap();
     for(int i=m;i<=n1;i++)
       {
         jobNode x=abc.removemin(); 
         System.out.println("移出x="+x.time);
         x.time=x.time+d[i].time;
         abc.insert(x);
       }
        abc.outMinHeap(); 
   }
}