25.8. JEditorPane | Introduction to Java Programming-Comprehensive Version (6th Edition)

[Page 757 ( continued )]

23.6. Heap Sort

Heap sort uses a binary heap to sort an array. The binary heap, introduced in §20.5, "Heaps," can be visualized as a complete binary tree. Each node in the tree is greater than or equal to its descendants, as shown in Figure 23.6(a). Recall that a binary heap can be implemented using an array, as shown in Figure 23.6(b). The root is at position 0, and its two children are at positions 1 and 2. For a node at position i , its left child is at position 2 i + 1 and its right child is at position 2 i + 2, and its parent is ( i - 1)/2. For example, the node for element 39 is at position 4, so its left child (element 14) is at 9 (2 x 4 + 1), its right child (element 33) is at 10 (2 x 4 + 2), and its parent (element 42) is at 1 ((4 “ 1)/2).

[Page 758]

Figure 23.6. A binary heap can be implemented using an array.

23.6.1. Sorting an Array from a Heap

Once you have such a heap, it is easy to obtain a sorted array as follows : Swap the root (i.e., the first element in the array) with the last leaf in the binary heap (i.e, the last element in the array). Remove the last element from the heap and rebuild heap. Repeat the swap and rebuild operations until the heap is empty. Figure 23.7(a) shows the tree after swapping the root with the last leaf. After this swap, the tree is no longer a heap. To rebuild a heap, use the following algorithm:

Listing 23.10. Algorithm for Rebuilding a Heap

 Let the root be the current node;   while   (the current node has children and the current node is smaller than one of its children) { Swap the current node with the larger of its children; Now the current node is one level down; }

Figure 23.7. Heap sort performs swap and rebuild operations.

Figure 23.7 shows the process of rebuilding a heap by swapping 9 with 59 in (b), swapping 9 with 44 in (c), and swapping 9 with 30 in (d).

[Page 759]

The algorithm is implemented in Listing 23.11.

Listing 23.11. Method for Rebuilding a Heap

 1   private static void   rebuildHeap(   int   [] list,   int   last) { 2   int   currentIndex =     ; 3   boolean   isHeap =   false   ; 4 5   while   (!isHeap) { 6   int   leftChildIndex =   2   * currentIndex +   1   ; 7   int   rightChildIndex =   2   * currentIndex +   2   ; 8   int   maxIndex = currentIndex; 9 10   if   (leftChildIndex <= last && 11 list[maxIndex] < list[leftChildIndex]) { 12 maxIndex = leftChildIndex; 13 } 14 15   if   (rightChildIndex <= last && 16 list[maxIndex] < list[rightChildIndex]) { 17 maxIndex = rightChildIndex; 18 } 19 20   if   (maxIndex != currentIndex) { 21  // Swap list[currentIndex] with list[maxIndex]  22   int   temp = list[currentIndex]; 23 list[currentIndex] = list[maxIndex]; 24 list[maxIndex] = temp; 25 currentIndex = maxIndex; 26 } 27   else   { 28 isHeap =   true   ; 29 } 30 } 31 }

The method rebuilds a heap in array list[0..last] . Before invoking the method, all the nodes in the tree represented in array list[0..last] satisfy the heap property except list[0] . The method starts from list[0] , compares it with its children, and stores the index of the largest value in maxIndex . Line 20 checks whether maxIndex is currentIndex . If so, the current node is greater than its children. In this case, the tree is a heap now (line 27). If not, swap the current node with the larger of its two children at position maxIndex and continue to move the current node down to the next level.

23.6.2. Creating an Initial Heap

You know how to produce a sorted array from a heap. Now the question is how to create a heap from an arbitrary array list initially. You may create a heap by adding a node to the tree one at a time. The heap initially contains list[0] as the root. Add list[1] to the heap. Swap list[0] with list[1] if list[0] < list[1] . Suppose that list[0..k-1] is already a heap. To add list[k] into the heap, consider list[k] as the last node in the existing heap. Compare it with its parent and swap them if list[k] is greater than its parent. Continue the compare and swap operations until list[k] is put in the right place in the heap. Figure 23.8 illustrates the process of adding element 88 to an existing heap (59 42 44 32 39 30 13 22 29 14 33 17).

Figure 23.8. A new element is added to the heap.

(This item is displayed on page 760 in the print version)

Listing 23.12 presents a method for making list[0..k] a heap, assume that list[0..k-1] is already a heap.

[Page 760]

Listing 23.12. Method for Making a Heap

 1  /** Assume list[0..k-1] is a heap, add list[k] to the heap */  2   private static void   makeHeap(   int   [] list,   int   k) { 3   int   currentIndex = k; 4 5   while   (currentIndex >     && 6 list[currentIndex] > list[(currentIndex -   1   ) /   2   ]) { 7  // Swap list[currentIndex] with list[(currentIndex -    1    ) /    2    ]  8   int   temp = list[currentIndex]; 9 list[currentIndex] = list[(currentIndex -   1   ) /   2   ]; 10 list[(currentIndex -   1   ) /   2   ] = temp; 11 12 currentIndex = (currentIndex -   1   ) /   2   ; 13 } 14 }

The method constructs a heap in array list[0..k] . Before invoking the method, all the nodes in the tree represented in array list[0..k-1] already form a heap. The method starts from list[k] , compares it with its parent, and swaps it with its parent if list[k] is greater than its parent (lines 8 “10). Continue to move the new element up to the root or it is less than its parent in the while loop.

23.6.3. Heap Sort Implementation

The complete heap sort algorithm can be implemented in Listing 23.13. The algorithm first creates a heap by adding one element from an array at a time (lines 4 “6), and then sorts the array by repeatedly removing the root from the heap (line 9 “15).

Listing 23.13. HeapSort.java

(This item is displayed on pages 760 - 761 in the print version)

 1   public class   HeapSort { 2   public static void   heapSort(   int   list[]) { 3  // Create a heap from the list

[Page 761]

 4   for   (   int   i =   1   ; i < list.length; i++) { 5 makeHeap(list, i); 6 } 7 8  // Produce a sorted array from the heap  9   for   (   int   last = list.length -   1   ; last >     ; ) { 10  // Swap list[       ] with list[last]  11   int   temp = list[last]; 12 list[last] = list[     ]; 13 list[     ] = temp; 14 rebuildHeap(list, “ “last); 15 } 16 } 17 18  /** Assume list[0..k-1] is a heap, add list[k] to the heap */  19   private static void   makeHeap(   int   [] list,   int   k) { 20  // Same as in Listing 23.12, so omitted  21 } 22 23   private static void   rebuildHeap(   int   [] list,   int   last) { 24  // Same as in Listing 23.11, so omitted  25 } 26 }

23.6.4. Heap Sort Analysis

Let h denote the height for a heap of n elements. Since a heap is a complete binary tree, the first level has 1 node, the second level has 2 nodes, the k th level has 2 ^{k - 1} nodes, the h - 1th level has 2 ^{h - 2} nodes, and the h th level has at least one node and at most 2 ^{h - 1} nodes. Therefore,

1 + 2 + ... + 2 ^{h - 2} < n less-than or equal to 1 + 2 + ... + 2 ^{h - 2} + 2 ^{h - 1}

i.e.,

2 ^{h - 1} - 1 < n less-than or equal to 2 ^h - 1

So, log( n + 1) less-than or equal to h < log( n + 1) + 1. Hence, the height of the heap is O (log n ).

Since the makeHeap method traces a path from a leaf to a root, it takes at most h steps to add a new element to the heap. Since the makeHeap method is invoked n times, the total time for constructing an initial heap is O ( n log n ). Since the rebuildHeap method traces a path from a root to a leaf, it takes at most h steps to rebuild a heap after removing the root from the heap. Since the rebuildHeap method is invoked n times, the total time for producing a sorted array from a heap is O ( n log n ).

Both merge sort and heap sort requires O ( n log n ) time. Merge sort requires a temporary array for merging two subarrays. Heap sort does not need additional array space. So, heap sort is more space efficient than merge sort.