Optimizing Heap Sort
In the heap sort from the previous section, we allocated extra space to construct the heap and sort it. In this section, we optimize this by using in-place heap sort.
For a max heap, first swap the data at the starting position with the value at the end of the array, so the end of the array becomes the maximum element. Then perform a shift down operation on element W to regenerate the max heap. Next, swap the newly generated maximum value with the second-to-last position of the entire array, so that the second-to-last position holds the second-largest data. This process continues by analogy.
The entire process can be illustrated by the following diagram:
Java example code
Source code package download:Download
src/example/heap/HeapSort.java file code:
package example.heap;
import example.sort.SortTestHelper;
/**
* In-place heap sort
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// Note that our heap is indexed starting from 0 at this point
// Start from (index of last element - 1) / 2
// The index of the last element is n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// Swap the two elements at indices i and j in the heap
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Original shiftDown process
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
// Left child node
int j = 2 * k + 1;
// The right child node is larger than the left child node
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
// Larger than both child nodes
if (arr[k].compareTo(arr[j]) >= 0) break;
// Swap the values of the original node and the child node
swap(arr, k, j);
k = j;
}
}
// Test HeapSort
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// Gradually extract the data in heapify using extractMax
// The extraction order should be from largest to smallest
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
// Ensure the arr array is sorted from largest to smallest
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}
}
import example.sort.SortTestHelper;
/**
* In-place heap sort
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// Note that our heap is indexed starting from 0 at this point
// Start from (index of last element - 1) / 2
// The index of the last element is n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// Swap the two elements at indices i and j in the heap
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Original shiftDown process
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
// Left child node
int j = 2 * k + 1;
// The right child node is larger than the left child node
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
// Larger than both child nodes
if (arr[k].compareTo(arr[j]) >= 0) break;
// Swap the values of the original node and the child node
swap(arr, k, j);
k = j;
}
}
// Test HeapSort
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// Gradually extract the data in heapify using extractMax
// The extraction order should be from largest to smallest
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
// Ensure the arr array is sorted from largest to smallest
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}
}