堆排序¶

堆排序（Heap Sort）是利用堆这种数据结构实现的一种排序算法。

堆¶

• 堆总是一棵完全二叉树。(完全二叉树是指即除了最底层，其他层的节点都必须被元素填满。)
• 堆中的任意节点的值都必须大于等于或小于等于它的子节点。
• 将每个节点的值都大于等于其子节点值的堆称为“大顶堆”(max heap)，将每个节点的值小于等于子节点值的堆称为“小顶堆”(min heap)。

算法描述¶

1. 堆排序通常使用大顶堆（max heap）
2. 先heapify将一个数组变成大顶堆。步骤是
   1. 从下标n/2的位置开始，和其子节点们比较，并不断向前移动。
   2. 如果节点比子节点小，则交换位置。
3. 用大顶堆实现堆排序
   1. 堆顶元素即为整个数据中的最大值，将堆顶元素与堆中最后一个元素交换，即将堆中最大元素放在了数组中的最后一个位置。最后一个元素完成排序。
   2. 由于将较小的元素放在了堆顶，对这个元素实行heapify。
   3. 重复第1和第2步，直到最后只剩堆顶元素。

Java¶

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {21, 100, 3, 50, 11};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    // O(n log n)
    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}