数据结构-树-堆-堆排序

在了解过堆的基础知识之后，我们看下堆排序
堆排序是指将给定的一串数据通过建堆之后再排序输出的过程。可以大致分为建堆和排序两个大步骤

建堆

建堆是指将给定数组原地按找堆的要求排列数据，其中原地的意思是指不依赖额外的内存空间（常量级的内存空间不算）。建堆的过程同样可以分为自下而上和自上而下，下面分别说下这两种的做法。

自下而上建堆

自下而上建堆其实和插入很相似，虽然我们数组有n个元素，但是我们依然可以假设堆中只有一个元素，即下标为1的元素，下标2 -- n的元素，我们通过插入的过程去插入这个堆中，因为插入就是自下而上堆化的过程，所以这种建堆方式也就是自下而上建堆。

自上而下建堆

自上而下建堆其实也很好理解，而且可能更常用，因为他可以省略处理所有的叶子节点。我们知道删除堆顶元素的时候，有提到自上而下堆化的过程，自上而下建堆其实和他很类似，只不过不是从堆顶开始的。我们知道叶子节点是没有子节点的，所以自上而下的建堆可以直接从第一个非叶子节点开始（这里的第一个指的是从叶子节点往前数的第一个非叶子节点）依次执行自上而下的堆化步骤，直到处理完堆顶节点，即完成自上而下建堆动作。可能文字上理解会有困难，我们直接看自上而下建堆的代码吧

package tree;

/**
 * @author TioSun
 */
public class Heap {

    private static void buildHeap(int[] a, int count) {
        for (int i = count / 2; i >= 1; --i) {
            heapify(a, count, i);
        }
    }

    private static void heapify(int[] a, int count, int i) {
        while (true) {
            // 需要交换的目标位置，先设为当前位置以表示无需交换
            int targetIndex = i;
            // 尝试和左子节点比较
            if (i * 2 < count && a[i] < a[i * 2]) {
                // 将交换位置暂定为左子节点
                targetIndex = i * 2;
            }
            // 尝试和右子节点比较
            if (i * 2 + 1 < count && a[targetIndex] < a[i * 2 + 1]) {
                targetIndex = i * 2 + 1;
            }
            if (targetIndex == i) {
                // 无需交换
                break;
            }
            // 与待交换位置的元素交换
            int temp = a[i];
            a[i] = a[targetIndex];
            a[targetIndex] = temp;

            i = targetIndex;
        }
    }
}

说好了建堆，接下来看看堆排序的过程吧

堆排序

我们直到对于大顶堆而言，堆顶元素就是这个数组的最大值（小顶堆就是最小值），还记得删除堆顶元素的步骤吗？我们将堆顶元素和最后一个元素交换，然后再从堆顶开始向下堆化剩余数据（指除最后一个元素外的数据，这个时候最后一个元素是要被删除的原堆顶元素），其实删除的数据还在数组中，只不过我们标记不可用了，那重复此步骤直到删完堆中的所有元素，数组中的数据是否就有序排布了（大顶堆就是升序，小顶堆就是降序）。我们来看下代码

/**
     * 依赖堆进行排序
     * @param a 待排序数组，要求下标需要从1开始
     * @param count 数组中的数据个数
     */
    public static void sort(int[] a, int count) {
        buildHeap(a, count);
        // 剩余个数
        int residueCount = count;

        while (residueCount > 1) {
            // 将堆顶元素和剩余的待排序中的最后一个元素交换
            swap(a, 1, residueCount);
            --residueCount;
            heapify(a, residueCount, 1);
        }
    }

private static void heapify(int[] a, int count, int i) {
        while (true) {
            // 需要交换的目标位置，先设为当前位置以表示无需交换
            int targetIndex = i;
            // 尝试和左子节点比较
            if (i * 2 < count && a[i] < a[i * 2]) {
                // 将交换位置暂定为左子节点
                targetIndex = i * 2;
            }
            // 尝试和右子节点比较
            if (i * 2 + 1 < count && a[targetIndex] < a[i * 2 + 1]) {
                targetIndex = i * 2 + 1;
            }
            if (targetIndex == i) {
                // 无需交换
                break;
            }
            // 与待交换位置的元素交换
            int temp = a[i];
            a[i] = a[targetIndex];
            a[targetIndex] = temp;

            i = targetIndex;
        }
    }