public class HeapSortDemo
1: //HeapSortDemo.java
3: import java.util.Arrays;
5: public class HeapSortDemo
6: {
7: // Binary max heap percolate down
8: static void maxHeapPercolateDown
9: (
10: int nodeIndex,
11: int[] heapArray,
12: int heapSize
13: )
14: {
15: int childIndex = 2 * nodeIndex + 1;
16: int value = heapArray[nodeIndex];
18: while (childIndex < heapSize)
19: {
20: // Find the max among the node and all the node's children
21: int maxValue = value;
22: int maxIndex = -1;
23: int i = 0;
24: while (i < 2 && i + childIndex < heapSize)
25: {
26: if (heapArray[i + childIndex] > maxValue)
27: {
28: maxValue = heapArray[i + childIndex];
29: maxIndex = i + childIndex;
30: }
31: i++;
32: }
34: if (maxValue == value)
35: {
36: return;
37: }
39: // Swap heapArray[nodeIndex] and heapArray[maxIndex]
40: int temp = heapArray[nodeIndex];
41: heapArray[nodeIndex] = heapArray[maxIndex];
42: heapArray[maxIndex] = temp;
44: nodeIndex = maxIndex;
45: childIndex = 2 * nodeIndex + 1;
46: }
47: }
49: // Sorts the array of numbers using the heap sort algorithm
50: static void heapSort(int[] numbers)
51: {
52: // Heapify numbers array
53: int i = numbers.length / 2 - 1;
54: while (i >= 0)
55: {
56: maxHeapPercolateDown(i, numbers, numbers.length);
57: i--;
58: }
60: i = numbers.length - 1;
61: while (i > 0)
62: {
63: // Swap numbers[0] and numbers[i]
64: int temp = numbers[0];
65: numbers[0] = numbers[i];
66: numbers[i] = temp;
68: maxHeapPercolateDown(0, numbers, i);
69: i--;
70: }
71: }
73: public static void main(String[] args)
74: {
75: int[] numbers = { 82, 36, 49, 82, 34, 75, 18, 9, 23 };
76: System.out.println("UNSORTED: " + Arrays.toString(numbers));
78: heapSort(numbers);
79: System.out.println("SORTED: " + Arrays.toString(numbers));
80: }
81: }