HeapSorter.java.html

  1  /**
  2     The sort method of this class sorts an array, using the heap 
  3     sort algorithm.
  4  */
  5  public class HeapSorter
  6  {
  7     /**
  8        Sorts an array, using selection sort.
  9        @param a the array to sort
 10     */
 11     public static void sort(int[] a)
 12     {  
 13        int n = a.length - 1;
 14        for (int i = (n - 1) / 2; i >= 0; i--)
 15        {
 16           fixHeap(a, i, n);
 17        }
 18        while (n > 0)
 19        {
 20           ArrayUtil.swap(a, 0, n);
 21           n--;
 22           fixHeap(a, 0, n);
 23        }
 24     }
 25  
 26     /**
 27        Ensures the heap property for a subtree, provided its
 28        children already fulfill the heap property.
 29        @param a the array to sort
 30        @param rootIndex the index of the subtree to be fixed
 31        @param lastIndex the last valid index of the tree that 
 32        contains the subtree to be fixed
 33     */
 34     private static void fixHeap(int[] a, int rootIndex, int lastIndex)
 35     {
 36        // Remove root
 37        int rootValue = a[rootIndex];
 38  
 39        // Promote children while they are larger than the root      
 40  
 41        int index = rootIndex;
 42        boolean more = true;
 43        while (more)
 44        {
 45           int childIndex = getLeftChildIndex(index);
 46           if (childIndex <= lastIndex)
 47           {
 48              // Use right child instead if it is larger
 49              int rightChildIndex = getRightChildIndex(index);
 50              if (rightChildIndex <= lastIndex
 51                    && a[rightChildIndex] > a[childIndex])
 52              {
 53                 childIndex = rightChildIndex;
 54              }
 55              
 56              if (a[childIndex] > rootValue) 
 57              {
 58                 // Promote child
 59                 a[index] = a[childIndex];
 60                 index = childIndex;
 61              }
 62              else
 63              {
 64                 // Root value is larger than both children
 65                 more = false;
 66              }
 67           }
 68           else 
 69           {
 70              // No children
 71              more = false; 
 72           }
 73        }
 74  
 75        // Store root value in vacant slot
 76        a[index] = rootValue;
 77     }
 78  
 79     /**
 80        Returns the index of the left child.
 81        @param index the index of a node in this heap
 82        @return the index of the left child of the given node
 83     */
 84     private static int getLeftChildIndex(int index)
 85     {
 86        return 2 * index + 1;
 87     }
 88  
 89     /**
 90        Returns the index of the right child.
 91        @param index the index of a node in this heap
 92        @return the index of the right child of the given node
 93     */
 94     private static int getRightChildIndex(int index)
 95     {
 96        return 2 * index + 2;
 97     }
 98  }