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 }