堆及堆排序

堆

堆是一种完全二叉树，分类有最大堆和最小堆。除了具备完全二叉树的特性外，最大堆的每个节点，都要大于其左右子树上的所有节点；最小堆的每个节点，都要小于其左右子树上的所有节点。要理解堆，就要明白堆是如何插入和删除节点，以及如何创建堆。

插入节点

将这些之前，先讲一下堆的存储结构。堆虽然是完全二叉树，但并不是链式存储，而是顺序存储。

例如我们现在给定数组：[ 1, 3, 2, 5, 6, 7, 4 ]（最小堆，接下来都会以该堆为例）

对于元素1，它的左右子节点为3和2；对于元素3，它的左右子节点为5和6；对于元素2，它的左右子节点为7和4；再之后的元素则没有子节点。由此观察，元素1的索引为0，则其子节点3和2的索引分别为2*0+1和2*0+2；元素3的索引为1，其子节点索引分别为2*1+1和2*1+2。即从堆的存储判断其左右子节点的公式为 2 * i + 1 和 2 * i + 2（ i 为索引）。

了解了存储结构，我们来看插入节点如何实现。

我们要插入节点0，那首先自然会扩展数组，然后把元素0置于末尾。接下来就要对节点进行上浮操作：

1. 将插入的节点与其父节点比较，若小于（因为这里是最小堆）父节点则将其与父节点交换。
2. 重复执行操作1，知道插入的节点大于父节点或者插入节点到达堆顶时，上浮操作完成。

我们来看一下图解过程：

删除节点

将刚才插入的元素0删除，其删除后会将末尾的节点置于堆顶，即节点5置于堆顶。此时发现不满足最小堆的结构于是我们要进行下沉操作：

1. 将需下沉节点与其左右子节点中比较小的一方交换
2. 重复操作1，直到该节点小于其左右子节点或者该节点已经是叶子节点时，下浮操作完成。

图解该过程：

我们可以看出删除后与最开始的堆是一样的，但其实这只是巧合。

创建堆

给出数据：[ 5, 2, 7, 3, 6, 1, 4 ]，创建最小堆：

将其看做完全二叉树：

从堆顶开始，由于 2 < 5，所以5下沉，2上浮。

此时 3 < 5，所以5下沉，3上浮。

再看到 1 < 7，所以7下沉，1上浮。

最后 1 < 2，所以2下沉，1上浮。

这样最小堆就创建结束了。

代码实现

private static int[] a; //堆存储数组
private static int size; //数组元素个数

/**
 * 交换函数，该函数用于交换数组中的两个元素
 *
 * @param m 交换元素下标
 * @param n 被交换元素下标
 */
private static void swap(int m, int n) {
    int temp = a[m];
    a[m] = a[n];
    a[n] = temp;
}

交换的过程在整个插入，删除中都经常使用，所以将其抽象成一个函数使用。

/**
 * 插入节点
 *
 * @param val 待插入节点
 */
public static void insert(int val) {
    //当元素个数大于数组长度时为数组扩容
    if (size > a.length - 1)
        a = Arrays.copyOf(a, size + 1);
    //新节点填入尾部
    a[size++] = val;

    //上浮操作
    int n = size - 1;
    while (true) {
        if ((n - 1) / 2 < 0 || a[n] >= a[(n - 1) / 2])
            break;
        swap(n, (n - 1) / 2);
        n = (n - 1) / 2;
    }
}

插入操作复杂度在于上浮操作，但上浮时交换次数最多为树的深度（时间复杂度O(logn)）。方法中(n - 1) / 2是获取父节点的公式，我们从 2 * i + 1 和 2 * i + 2 反推得到的。即让 n = 2 * i + 1 和 n = 2 * i + 2 结合int类型会去掉运算结果的小数部分得到 (n - 1) / 2

/**
 * 创建堆
 *
 * @param values
 */
public static void createHeap(int[] values) {
    a = values;
    size = 0;
    for (int i = 0; i < a.length; i++)
        insert(a[i]);
}

创建堆时size初始化为0，参数values只用于赋值给a，没有其他用处是为了强调任何排序都是原地进行的，所以我们创建堆，插入节点，删除节点以及堆排序都基于a数组原地进行。

创建堆的方法内部调用了插入节点方法。从创建堆的图解中发现，如果按照索引的方式下去，到最后一部的时候，发现了前面的节点又需要进行上浮下沉操作，这使得我们又要将索引往回推。所以我们直接一个一个插入节点去避免这个问题。

创建堆的时间复杂度是O(nlogn)。

/**
 * 删除节点
 * 
 * @param index 末尾元素与数组末尾的距离
 */
public static void delete(int index) {
    int n, temp, i, left, right;
        
    //将堆顶元素与末尾元素交换
    n = a.length - size;
    swap(0, n);

    //下沉操作
    i = 0;
    while (true) {
        left = 2 * i + 1;
        right = 2 * i + 2;
        if (left > n - 1)
            break;
        int min;
        if (right > n - 1)
            min = left;
        else
            min = (a[left] < a[right]) ? left : right;
        if (a[i] < a[min])
            break;
        swap(min, i);
        i = min;
    }
}

删除节点时，我们并不让其堆顶元素直接消失，而是将其置于数组末尾。然后使用参数index去将数组长度掩盖，这样就能使堆顶不断的排在数组末尾。该方法时间复杂度是O(logn)。

/**
 * 堆排序
 */
public static void heapSort() {
    for (int i = 1; i <= a.length; i++)
        delete(i);
    for (int i = 0; i < a.length / 2; i++)
        swap(i, a.length - i - 1);
}

上述的删除节点，我们也可以真正的删除，但之所以不真正删除是为了来做排序。我们了解到上述删除会将堆顶置于末尾，我们来看是如何实现的：

1. [ 1, 3, 2, 5, 6, 7, 4 ]
2. [ 4, 3, 2, 5, 6, 7, 1 ] => [ 2, 3, 4, 5, 6, 7, 1 ]
3. [ 7, 3, 4, 5, 6, 2, 1 ] => [ 3, 5, 4, 7, 6, 2, 1 ]
4. [ 6, 5, 4, 7, 3, 2, 1 ] => [ 4, 5, 6, 7, 3, 2, 1 ]
5. [ 7, 5, 6, 4, 3, 2, 1 ] => [ 5, 7, 6, 4, 3, 2, 1 ]
6. [ 6, 7, 5, 4, 3, 2, 1 ] => [ 7, 6, 5, 4, 3, 2, 1 ]
7. [ 7, 6, 5, 4, 3, 2, 1 ]

可以看出最后是一个逆序的数组。也就是当我们堆排序方法的第一个for循环执行后的结果。我们再让其进行倒序得到顺序的数组。时间复杂度是O(nlogn)。

完整代码

public class Heap {
    private static int[] a; //堆存储数组
    private static int size; //数组元素个数

    /**
     * 插入节点
     *
     * @param val 待插入节点
     */
    public static void insert(int val) {
        if (size > a.length - 1)
            a = Arrays.copyOf(a, size + 1);
        //新节点填入尾部
        a[size++] = val;

        //上浮操作
        int n = size - 1;
        while (true) {
            if ((n - 1) / 2 < 0 || a[n] >= a[(n - 1) / 2])
                break;
            swap(n, (n - 1) / 2);
            n = (n - 1) / 2;
        }
    }

    /**
     * 创建堆
     *
     * @param values
     */
    public static void createHeap(int[] values) {
        a = values;
        size = 0;
        for (int i = 0; i < a.length; i++)
            insert(a[i]);
    }

    /**
     * 删除节点
     *
     * @param index 末尾元素与数组末尾的距离
     */
    public static void delete(int index) {
        int n, temp, i, left, right;

        //将堆顶元素与末尾元素交换
        n = a.length - index;
        swap(0, n);

        //下沉操作
        i = 0;
        while (true) {
            left = 2 * i + 1;
            right = 2 * i + 2;
            if (left > n - 1)
                break;
            int min;
            if (right > n - 1)
                min = left;
            else
                min = (a[left] < a[right]) ? left : right;
            if (a[i] < a[min])
                break;
            swap(min, i);
            i = min;
        }
    }

    /**
     * 堆排序
     */
    public static void heapSort() {
        for (int i = 1; i <= a.length; i++)
            delete(i);
        for (int i = 0; i < a.length / 2; i++)
            swap(i, a.length - i - 1);
    }

    /**
     * 交换函数，该函数用于交换数组中的两个元素
     *
     * @param m 交换元素下标
     * @param n 被交换元素下标
     */
    private static void swap(int m, int n) {
        int temp = a[m];
        a[m] = a[n];
        a[n] = temp;
    }

    public static void main(String[] args) {
        // 创建堆
        int[] values = {5, 2, 7, 3, 6, 1, 4};
        createHeap(values);
        System.out.println(Arrays.toString(a));

        // 堆排序
        heapSort();
        System.out.println(Arrays.toString(a));
    }
}

mian函数测试结果：