排序算法系列——堆排序

堆排序同直接选择排序一样是选择排序的一种。堆排序是借助一种数据结构——堆来完成排序，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
什么是堆：
关于二叉树这里就不叙述了。堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

从上面可以看出，如果对一个堆从上往下，从左往右进行遍历的话，正好和数组的顺序是一致的。所以对于给定一个节点（下标i）我们可以很容易计算出其子节点以及父节点的下标：

• Parent(i) = floor(i/2)，i 的父节点下标
• Left(i) = 2i，i 的左子节点下标
• Right(i) = 2i + 1，i 的右子节点下标

同时堆还有最大堆和最小堆之分。
最大堆：

• 堆的根节点是最大值
• 堆中每个节点都大于其子节点，小于其父节点

最小堆：

• 堆的根节点是最小值
• 堆中每个节点都小于其子节点，大于其父节点

基本思想：
堆排序就是利用堆这种特殊的数据结构来进行排序，比如我们选择最大堆来进行排序，则我们只需要将待排序的元素构建成一个堆即可，因为堆中的第一个元素是最大值，所以将堆的第一个元素取出，之后再将剩余的元素构建成一个新堆，再取出第一个元素，当所有的元素都被取出之后，整个序列就完成了排序。从描述可以看出，这里是利用堆来从无序部分中获取最大值，所以堆排序同直接选择排序的基本思想一样，都是从无序部分取出一个最大或者最小值放入有序部分，两者的不同之处在于直接选择排序是通过对无序部分进行遍历比较来获取最大值或者最小值，而堆排序是利用堆这种特殊的数据结构。
实现要点：
如果想要对一组数据使用堆排序，首先要做的就是将这组数据构建成一个堆，然后取出堆中的根节点。这里我们选择最大值，即根节点是最大值，为了减少排序的空间复杂度，我们将选出的元素直接与原数组的最后一位进行交换，这样数组的最后一位就是正确的了，然后我们对剩余元素重新调整成堆结构，重复此过程直到只剩下一个元素。
这里主要就是两个操作过程，一个是建堆，一个是调整堆。
在构建堆的时候一般选择最后一个元素的父节点作为起始点进行递归构建堆。建堆是一个递归的过程，即先构建最下层的小堆，然后逐步往外层构建，最终形成一个完整的堆，因为当一个节点大于其子节点，那么如果其父节点大于这个节点，则它的父节点比大于其孙子节点，所以整个堆都是满足条件的。
在调整堆的时候，由于调整堆是因为我们拿走了一个元素，所以在调整堆时需要注意整个堆的大小，这个大小会随着迭代的次数而逐步减小，最终为1。不同于建构堆，调整堆的时候由于我们将根节点与最后一个节点进行交换，所以我们从上而下进行调整，即将这个交换到根节点的元素逐步沉到其合理的位置。
Java实现：

package com.vicky.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 * 选择排序：堆排序
 * 
 * </p>
 * 
 * @author Vicky
 * @date 2015-8-13
 * @param <T>
 */
public class HeapSort {
    /**
     * 排序
     * 
     * @param data
     *            待排序的数组
     */
    public static <T extends Comparable<T>> void sort(T[] data) {
        long start = System.nanoTime();
        if (null == data) {
            throw new NullPointerException("data");
        }
        if (data.length == 1) {
            return;
        }
        buildMaxHeap(data);
        // 末尾与头交换，交换后调整最大堆
        for (int i = data.length - 1; i > 0; i--) {
            T temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            adjustMaxHeap(data, i, 0);
        }
        System.out.println("use time:" + (System.nanoTime() - start) / 1000000);
    }

    /**
     * 构建最大堆
     * 
     * @param <T>
     * @param data
     * @param index
     *            序列起始点
     */
    public static <T extends Comparable<T>> void buildMaxHeap(T[] data) {
        // 自下而上构建最大堆，即从最后一个元素的父节点开始构建最大堆
        int start = getParentIndex(data.length - 1);
        for (; start >= 0; start--) {
            adjustMaxHeap(data, data.length, start);
        }
    }

    /**
     * 调整最大堆，自下而上
     * 
     * @param <T>
     * @param data
     * @param heapsize
     *            堆的大小，即对data中从0开始到heapsize之间的元素构建最大堆
     * @param index
     *            当前需要构建最大堆的位置
     */
    public static <T extends Comparable<T>> void adjustMaxHeap(T[] data, int heapsize, int index) {
        // 获取该元素左右子元素
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);
        int max = index;
        // 取三个元素中最大值与父节点进行交换
        if (left < heapsize && data[max].compareTo(data[left]) < 0) {
            max = left;
        }
        if (right < heapsize && data[max].compareTo(data[right]) < 0) {
            max = right;
        }
        if (max != index) {
            swap(data, index, max);
            adjustMaxHeap(data, heapsize, max);
        }
    }

    /**
     * 交换元素
     * 
     * @param <T>
     * @param data
     * @param i
     * @param j
     */
    public static <T extends Comparable<T>> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * 获取父节点位置
     * 
     * @param i
     * @return
     */
    public static int getParentIndex(int i) {
        return (i - 1) >> 1;
    }

    /**
     * 获取左子节点位置
     * 
     * @param current
     * @return
     */
    public static int getLeftChildIndex(int current) {
        return (current << 1) + 1;
    }

    /**
     * 获取右子节点位置
     * 
     * @param current
     * @return
     */
    public static int getRightChildIndex(int current) {
        return (current << 1) + 2;
    }

    public static void main(String[] args) {
        Random ran = new Random();
        Integer[] data = new Integer[100000];
        for (int i = 0; i < data.length; i++) {
            data[i] = ran.nextInt(100000000);
        }
        HeapSort.sort(data);
        System.out.println(Arrays.toString(data));
    }
}

效率分析：

（1）时间复杂度
O(nlogn)
（2）空间复杂度
O(1)
-从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换O(1)。
（3）稳定性
不稳定。
考虑序列{5A,7,13,5B}，首先我们构建成一个堆，得到的堆是：{13,7,5A,5B}，现在我们取出根节点，然后跟最后一个元素进行交换，再重新调整堆，得到的堆是：{7,5B,5A}，再取走根节点，剩余的堆是：{5A,5B}，所以最终得到的排序结果是5B,5A,7,13。显示堆排序是不稳定的。
参考文章：
常见排序算法 - 堆排序 (Heap Sort)
堆排序
堆排序