01: /**
02:    This class implements a simple version 
03:    of the heapsort algorithm.
04: 
05:    Note that this algorithm assumes that
06:    the values to be sorted are in elements
07:    1 ... n of the array (not 0 ... n-1).
08: 
09:    The implementation is based on a sorting
10:    framework by Cay Horstmann.
11: 
12:    @author J. Mohr
13: */
14: public class HeapSort
15: {
16:    public HeapSort(int[] anArray)
17:    {
18:       a = anArray;
19:    }
20: 
21:    /**
22:       Sorts the array managed by this sorter
23:    */
24:    public void sort()
25:    {
26:       sort( a.length - 1 );
27:    }
28: 
29:    public void sort( int end )
30:    {
31:       // Establish the heap property.
32:       for ( int i = end / 2; i >= 1; i-- )
33:          fixHeap( i, end, a[i] );
34:       
35:       // Now place the largest element last,
36:       // 2nd largest 2nd last, etc.
37:       for ( int i = end; i > 1; i-- )
38:       {
39:          // a[1] is the next-biggest element.
40:          swap( 1, i );
41: 
42:          // Heap shrinks by 1 element.
43:          fixHeap( 1, i - 1, a[1] );
44:       }
45:    }
46: 
47:    /**
48:       Assuming that the partial order tree
49:       property holds for all descendants of
50:       the element at the root, make the
51:       property hold for the root also.
52: 
53:       @param root the index of the root
54:                     of the current subtree
55:       @param end  the highest index of the heap
56:    */
57:    private void fixHeap( int root, int end,
58:                          int key )
59:    {
60:       int child = 2 * root; // left child
61:       
62:       // Find the larger child.
63:       if ( child < end && a[child] < a[child + 1] )
64:          child++;  // right child is larger
65: 
66:       // If the larger child is larger than the
67:       // element at the root, move the larger child
68:       // to the root and filter the former root 
69:       // element down into the "larger" subtree.
70:       if ( child <= end && key < a[child] )
71:       {
72:          a[root] = a[child];
73:          fixHeap( child, end, key );
74:       }
75:       else
76:          a[root] = key;
77:    }
78: 
79:    /**
80:       Swaps two entries of the array.
81:       @param i the first position to swap
82:       @param j the second position to swap
83:    */
84:    private void swap(int i, int j)
85:    {
86:       int temp = a[i];
87:       a[i] = a[j];
88:       a[j] = temp;
89:    }
90: 
91:    private int[] a;
92: }