算法之堆排序/JAVA

0.5 优先队列与堆排序

• 什么是优先队列？优先队列是一种支持删除最大元素（或最小元素）和插入元素的数据结构，它适用于这样的一种情况。我们有巨大的数据量，同时还有输入，而我们也不需要将全部元素排序，我们只需要知道最大的元素即可。比较典型的应用就是模拟系统和任务调度，在任务调度中我们不需要对所有任务进行排序，我们只需要知道等待时间最久的元素即可，然后执行它，而这种情况下的输入数量无法确定，甚至可能是无限的。

下面我们从这样的一个场景进行分析，加入我们有一个有关科学实验的数据模型，我们有成千上万台机器在运算数据并输出，而我们只需要找到其中的最大的几个，所以我们需要一个算法在插入和删除（输出）的时间都较少。

下面我们比较下各个数据结构的时间

数据结构	插入元素	删除最大元素
有序数组	N	1
无序数组	1	N
堆	logN	logN

由此可见，堆应该是在我们上述情况下最好的一种数据结构。什么是堆？堆一般情况可以看作是一个完全二叉树的数组对象，其中每一个节点都大于等于它的两个子节点时，被称为堆有序。当一个有序堆储存在数组里是具有如下结构的。

从上图我们可以很容易的看出，当我嫩数组的0号位不存储数据时，我们可以很容易的将其抽象为一个堆，其中：

• 第k个子节点的父节点是k/2
• 第k个父节点的子节点是2k+1或2k+2

堆的相关概念我们已经了解了，那么如果我们某个元素被改变了我们如何将其再次变为堆有序呢

1. 由下而上的堆有序化

如果某个节点变得比其父节点更大，那我们只需要交换他和他的父节点来进行修复即可

可以看出我们有序化的过程异常简单。那么算法是如何实现的呢？

/**
  * 由下至上的堆排序
  * @param k 被改变的元素
  */
public static void swim(int k){
  //只要被改变的元素不是第一个并且大于k/2就一直交换k和k/2
  while (k > k/2 && k > 1) {
    exch(k/2, k );
    k = k/2;

  }
}

2. 由上而下的堆有序化

有了自下而上的有序化的经验，自上而下的堆有序化就不难理解，当一个节点变得比他的子节点更小了，我们就通过交换他与他两个子节点中最大的那个即可，但是我们要注意不要越界。

代码如下：

public static void sink(int k){
  //只要子节点存在
  while (2*k <= N){
    //定义临时变量设置子节点
    int j = 2*k;
    //如果左子节点小于右子节点，则变为右节点
    if (j < N && less(j,j+1)){
      j++;
    }
    //如果子节点大于自己则跳出
    if (less(j,k)){
      break;
    }
    exch(k,j);
    k = j;
  }
}

0.5.1 堆排序

堆排序可以分作两个阶段，我们将原始数组重新组织安排进一个堆中，然后将堆有序化。然后再从堆中按递减顺序取出所有元素得到结果（每次都是取出根节点，然后将堆有序化即可，如此往复）即可获得排好序的数组。

• 因为上方我们是将数组从1开始建堆，但是我们实际应用中数组都是从0开始储存数据，所以我们需要稍微改动下有序化方法。如下：

/**
     * 因为堆在数组从1开始才具有当前节点为k，父节点为k/2
     * 但是我们的数组是从0开始的，所以我们要将0虚拟成1
     * 方法就是将0+1
     * 但是这样我们虚拟的数组的第4位其实存在于真实数组的第三位
     * 所以要将j-1才能取到正确的值
     * @param a
     * @param k
     * @param N
     */
    public static void sink(Comparable[] a,int k,int N){
        //只要子节点存在
        while (2*(k+1) <= N){
            //定义临时变量设置子节点
            int j = 2*(k+1);
            //如果左子节点小于右子节点，则变为右节点
            if (j+1 <= N && less(a[j-1],a[j])){
                j++;
            }
            //如果子节点大于自己则跳出
            if (less(a[j-1],a[k])){
                break;
            }
            exch(a,k,j-1);
            k = j-1;
        }
    }

• 堆排序算法如下

public class Heap {
    /**
     * 具体算法实现
     */
    public static void sort(Comparable[] a) {

        int N = a.length;
        for (int k = N/2; k >= 0; k--) {
            sink(a,k,N);
        }

        /**
         * 将第0个和最后一个交换，然后将堆的长度-1
         * 然后将堆有序化
         */
        while (N >= 1){
            exch(a,0 ,N-1);
            N--;
            sink(a,0,N);
        }
    }

    /**
     * 因为堆在数组从1开始才具有当前节点为k，父节点为k/2
     * 但是我们的数组是从0开始的，所以我们要将0虚拟成1
     * 方法就是将0+1
     * 但是这样我们虚拟的数组的第4位其实存在于真实数组的第三位
     * 所以要将j-1才能取到正确的值
     * @param a
     * @param k
     * @param N
     */
    public static void sink(Comparable[] a,int k,int N){
        //只要子节点存在
        while (2*(k+1) <= N){
            //定义临时变量设置子节点
            int j = 2*(k+1);
            //如果左子节点小于右子节点，则变为右节点
            if (j+1 <= N && less(a[j-1],a[j])){
                j++;
            }
            //如果子节点大于自己则跳出
            if (less(a[j-1],a[k])){
                break;
            }
            exch(a,k,j-1);
            k = j-1;
        }
    }

    /**
     * 对两个元素进行比较，如果v<w返回true
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v ,Comparable w){
        /**
         * compareTo 方法
         * 返回为正数表示v>w, 返回为负数表示v<w, 返回为0表示v==w
         */
        return v.compareTo(w) < 0;
    }

    /**
     * 交换a[i]和a[j]
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 输出数组
     * @param a
     */
    private static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /**
     * 测试数组是否有序
     * @param a
     * @return
     */
    private static boolean isSort(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            if (less(a[i],a[i-1])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        String[] a = {"5","3","6","5","7","9","2","1","3","8"};

        sort(a);
        assert isSort(a);
        show(a);
    }

}

特点：

• 堆排序的效率都达到了基于比较的排序算法效率的峰值
• 时间复杂度为O(nlogn)
• 只需要O(1)的辅助空间
• 最坏情况下时间复杂度仍为O(nlogn)
• 稳定的排序算法