SORTING - Introduction to Java Programming: Comprehensive Version - page 879

45 int leftChildIndex = 2 * currentIndex + 1 ;

46 int rightChildIndex = 2 * currentIndex + 2 ;

47
48 // Find the maximum between two children
49 if (leftChildIndex >= list.size()) break ; // The tree is a heap
50 int maxIndex = leftChildIndex;
51 if (rightChildIndex < list.size()) {
52 if (list.get(maxIndex).compareTo(
53 list.get(rightChildIndex)) < 0 ) {
54 maxIndex = rightChildIndex;
55 }
56 }
57
58 // Swap if the current node is less than the maximum
59 if (list.get(currentIndex).compareTo(
60 list.get(maxIndex)) < 0 ) {
61 E temp = list.get(maxIndex);
62

compare two children

swap with the larger child

list.set(maxIndex, list.get(currentIndex));

63 list.set(currentIndex, temp);

64 currentIndex = maxIndex;

65 }
66 else

67 break ; // The tree is a heap

68 }
69
70 return removedObject;

71 }
72
73 /** Get the number of nodes in the tree */

74 public int getSize() {

75 return list.size();

76 }
77 }

A heap is represented using an array list internally (line 2). You can change the array list to
other data structures, but the Heap class contract will remain unchanged.
The add(E newObject) method (lines 15-33) appends the object to the tree and then
swaps the object with its parent if the object is greater than its parent. This process continues
until the new object becomes the root or is not greater than its parent.
The remove() method (lines 36-71) removes and returns the root. To maintain the heap
property, the method moves the last object to the root position and swaps it with its larger
child if it is less than the larger child. This process continues until the last object becomes a
leaf or is not less than its children.

23.6.5 Sorting Using the Heap Class
To sort an array using a heap, first create an object using the Heap class, add all the ele-
ments to the heap using the add method, and remove all the elements from the heap using
the remove method. The elements are removed in descending order. Listing 23.10 gives a
program for sorting an array using a heap.

L ISTING 23.10

HeapSort.java
1 public class HeapSort {
2 /** Heap sort method */
3 public static <E extends Comparable<E>> void heapSort(E[] list) {
4 // Create a Heap of integers
5 Heap<E> heap = new Heap<>();
6

create a Heap