001: /**
002:    This class applies the heapsort algorithm to sort an array.
003: */
004: public class HeapSorter
005: {
006:    /**
007:       Constructs a heap sorter that sorts a given array.
008:       @param anArray an array of integers
009:    */
010:    public HeapSorter(int[] anArray)
011:    {
012:       a = anArray;
013:    }   
014: 
015:    /**
016:       Sorts the array managed by this heap sorter.
017:    */
018:    public void sort()
019:    {  
020:       int n = a.length - 1;
021:       for (int i = (n - 1) / 2; i >= 0; i--)
022:          fixHeap(i, n);
023:       while (n > 0)
024:       {
025:          swap(0, n);
026:          n--;
027:          fixHeap(0, n);
028:       }
029:    }
030: 
031:    /**
032:       Ensures the heap property for a subtree, provided its
033:       children already fulfill the heap property.
034:       @param rootIndex the index of the subtree to be fixed
035:       @param lastIndex the last valid index of the tree that 
036:       contains the subtree to be fixed
037:    */
038:    private void fixHeap(int rootIndex, int lastIndex)
039:    {
040:       // Remove root
041:       int rootValue = a[rootIndex];
042: 
043:       // Promote children while they are larger than the root      
044: 
045:       int index = rootIndex;
046:       boolean more = true;
047:       while (more)
048:       {
049:          int childIndex = getLeftChildIndex(index);
050:          if (childIndex <= lastIndex)
051:          {
052:             // Use right child instead if it is larger
053:             int rightChildIndex = getRightChildIndex(index);
054:             if (rightChildIndex <= lastIndex
055:                   && a[rightChildIndex] > a[childIndex])
056:             {
057:                childIndex = rightChildIndex;
058:             }
059:             
060:             if (a[childIndex] > rootValue) 
061:             {
062:                // Promote child
063:                a[index] = a[childIndex];
064:                index = childIndex;
065:             }
066:             else
067:             {
068:                // Root value is larger than both children
069:                more = false;
070:             }
071:          }
072:          else 
073:          {
074:             // No children
075:             more = false; 
076:          }
077:       }
078: 
079:       // Store root value in vacant slot
080:       a[index] = rootValue;
081:    }
082: 
083:    /**
084:       Swaps two entries of the array.
085:       @param i the first position to swap
086:       @param j the second position to swap
087:    */
088:    private void swap(int i, int j)
089:    {
090:       int temp = a[i];
091:       a[i] = a[j];
092:       a[j] = temp;
093:    }
094: 
095:    /**
096:       Returns the index of the left child.
097:       @param index the index of a node in this heap
098:       @return the index of the left child of the given node
099:    */
100:    private static int getLeftChildIndex(int index)
101:    {
102:       return 2 * index + 1;
103:    }
104: 
105:    /**
106:       Returns the index of the right child.
107:       @param index the index of a node in this heap
108:       @return the index of the right child of the given node
109:    */
110:    private static int getRightChildIndex(int index)
111:    {
112:       return 2 * index + 2;
113:    }
114: 
115:    private int[] a;
116: }