Subversion Repositories programming

Rev

Rev 54 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 54 Rev 55
Line 128... Line 128...
128 
 
 128 
 
129 
    private static void heapify( Comparable[] a, int i, int n ) {
 129 
    private static void heapify( Comparable[] a, int i, int n ) {
130 
        Comparable ai = a[i];
 130 
        Comparable ai = a[i];
131 
        while( i < n/2 ) {                       // a[i] is not a leaf
 131 
        while( i < n/2 ) {                       // a[i] is not a leaf
132 
            int j = 2*i+1;                       // a[j] is ai¿s left child
 132 
            int j = 2*i+1;                       // a[j] is ai¿s left child
133 
            if( j+1 < n && a[j+1].compareTo(a[j]) > 0 ) ++j;  // a[j] is ai¿s larger child
 133 
            if( j+1 < n && a[j+1].compareTo(a[j]) > 0 ) ++j;  // a[j] is ai's larger child
134 
            if( a[j].compareTo(ai) <= 0 ) break;              // a[j] is not out of order
 134 
            if( a[j].compareTo(ai) <= 0 ) break;              // a[j] is not out of order
135 
            a[i] = a[j];                         // promote a[j]
 135 
            a[i] = a[j];                         // promote a[j]
136 
            i = j;                               // move down to the next level
 136 
            i = j;                               // move down to the next level
137 
        }
 137 
        }
138
138