四、堆排序
上面已经解释了什么是堆，如果使堆中每个节点波爱吃最大堆的性质，并且也创建了最大堆。以上3个步骤的目的都是为了堆排序准备的，现在有一个疑问最大堆是排序好的数组吗？要想解决这个疑惑可以直接查看三种创建最大的堆的结果，看下其结果（[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]）是否满足排序要求，猛的一看好像是满足由大到小一次排序，但是其中7与2明显小于右侧的值，所以最大堆并不一定都是排序好的数组。 最大堆有一个特点，其根节点是堆中最大的，如果能把根节点从堆中移除，再接着把剩余的结点保持最大堆特性，反复移除与保持剩余节点的最大堆操作，因为每次移除的都是剩余节点中值最大的，所以可能创建一个排序好数组。（1） 堆排序伪码
其中BUILD-MAX-HEAP在（二、保持堆的性质）已经介绍，MAX-HEAPIFY在（三、创建最大堆）已经介绍HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i ← length[A] downto 2 3 do exchange A[1] <-> A[i] 4 heap-size[A] ← heap-size[A] - 1 5 MAX-HEAPIFY(A, 1)
（2）堆排序完整代码
public class HeapSort {
public static void main(String[] args) {
int[] array = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
System.out.println( Arrays.toString(array) );
HeapSort heapSort = new HeapSort();
heapSort.heapSort(array, array.length);
System.out.println( Arrays.toString(array) );
}
public void heapSort(int[] array, int n) {
if (array == null) {
throw new NullPointerException();
}
if (n > array.length) {
throw new ArrayIndexOutOfBoundsException();
}
buildMaxHeap(array, n);
for (int i = n-1; i >= 1; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
}
public void buildMaxHeap(int[] a, int n) {
for (int i = n/2-1 ; i >= 0; i--) {
maxHeapify(a, i, n);
}
}
private void maxHeapify(int[] a, int i, int n) {
int largest;
int leftIndex = 2 * i + 1;
int rightIndex = leftIndex + 1;
if (leftIndex < n && a[leftIndex] > a[i]) {
largest = leftIndex;
} else {
largest = i;
}
if (rightIndex < n && a[rightIndex] > a[largest]) {
largest = rightIndex;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, n);
}
}
private void swap(int[] pArray, int pX, int pY) {
int temp = pArray[pX];
pArray[pX] = pArray[pY];
pArray[pY] = temp;
}
}
注意：maxHeapify方法与上面的不同，增加了参数n堆元素总个数，因为每次移除根后堆的大小都会减去1，所以每次创建最大堆的时候传入堆元素总个数的参数都是移除根后的值。
输入数组：[4, 1, 3, 2, 16, 9, 10, 14, 8, 7] 输出结果：[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
五、参考资料
《算法导论》 第六章 堆排序《精通八大排序算法系列：二、堆排序算法》 文中图片都是来自此文章，原始出处是《算法导论》
《白话经典算法系列之七 堆与堆排序》
《经典排序算法 - 堆排序Heap sort》
返回 Java 学习文章 - 索引