算法入门：堆排序

基础概念

堆排序是比较基础的排序算法，也是我认为比较难的一种算法，因为它的流程比较多，理解起来不会像冒泡排序和选择排序那样直观。
要理解堆排序，需要先理解二叉树：
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），而二叉树还有个名字叫做二叉堆（看起来一堆。。。）。
二叉堆是一棵被完全填满的二叉树，有例外的可能是底层元素，底层元素从左到右填入，这样的树被称为完全二叉树。
仔细观察可以发现，其实一个数组可以被表示成一个二叉树：

Paste_Image.png

左边为数组，而右边为数组的二叉树的表达方式。

观察上图可以发现，任意一位置i上元素，其左儿子为2i+1上，右儿子在2i+2上。

我们现在的需求是对数组元素进行从小到大排序，那么我们需要根据既定的数据构建堆，这也是堆排序必要的一步。在构建堆的时候，我们需要满足堆序性质。
堆序性质：任意一个节点小于（大于）它的后裔，这取决于你测排序方式。
这里以从小到大排序为例。那么，此时我们需要节点要小于它的后裔，那么这样我们就可以保证根节点是最小的元素。

堆排序主要分三步：
（1）.构建堆
（2）.调整堆
（3）.堆排序

首先需要明确一点，构建堆是在数组基础上构建的，换句话说就是将数组抽象成一个二叉堆，而不需要另构建。
在构建堆之前需要保证一点，构建之后的结构需要堆序性质，什么是堆序性质？
堆序性质所描述的是：在一个二叉堆中任意父节点大于其两个子节点。

堆排序的流程和实现

下面通过一个例子来看一下堆排序是一个怎样的流程。
首先要构建堆，构建堆其实是先将数组抽象成二叉堆之后调整堆的过程。
首先给定数组S、O、R、T、E、X、A、M、P、L、E，排序规则为字典序。
根据已知数组构建堆如下：

Paste_Image.png

上图可以看出来，初始的堆顺序和数组顺序是一致的。显然上图是不符合堆序性质的，那么接下来需要进行堆的调整。
调整堆时我们需要制定一个起始点进行调整，我们将这个起始点定为N/2，N为目标数组的长度。由于二叉堆是一个完全二叉树，那么N/2对应着倒数第二层，且有子节点的最后一个节点（没有子节点不需要进行调整）。那么这个节点是E节点index为5。由于E字典序小于L，同时需要构建大根堆，所以需要交换E和L。

Paste_Image.png

接下来调整到T节点，T节点大于下面两个节点，那么不需要进行调整。

Paste_Image.png

接下来到R节点，由于R小于X，所以进行交换：

Paste_Image.png

接下来调整到O节点，O节点比较特殊，它小于T节点同时小于P节点，所以O节点会下沉到最后一层。

Paste_Image.png

最后调整到S节点，由于S小于X，那么进行调整:

Paste_Image.png

调整之后的结构如上所示，上述堆结构保证了堆的有序，继而能确定全局的最大节点X。
构建堆的代码如下：

   /**
     * 此调整为从上到下调整，直到节点超出范围
     * @param data
     * @param heapSize
     * @param index
     */
    private static void maxHeap(String[] data,int heapSize,int index){
        //取得当前节点的左右节点，当前节点为index
        int left=getChildLeftIndex(index);
        int right=getChildRightIndex(index);
        //对左右节点和当前节点进行比较
        int largest=index;
        if(left<heapSize&&data[index].compareTo(data[left])<0){
            largest=left;
        }
        if(right<heapSize&&data[largest].compareTo(data[right])<0){
            largest=right;
        }
        //交换位置
        if(largest!=index){
            String temp=data[index];
            data[index]=data[largest];
            data[largest]=temp;
            maxHeap(data,heapSize,largest);
        }
    }
/**
     * 初始化构建堆
     * @param data
     */
    private static void buildMaxHeap(String[] data){
        //根据最后一个元素获取，开始调整的位置
        int startIndex=getParentIndex(data.length-1);
        //反复进行调整
        for(int i=startIndex;i>=0;i--){
            maxHeap(data,data.length,i);
        }
    }

其实搞定了调整堆，堆排序就成功了一半了，那么接下来需要做的是，循环N次，进行N次调整堆操作，每一次调整堆得到的最大值，将此值和数组的最后一个元素进行交换，交换后“减小”数组的长度（最后n个值不参与堆的调整），直到最后一个元素，就完成了堆的排序.
此过程是从上到下的调整过程，因为构建好之后的堆具有堆序性质，从根节点调整时只选择一个子节点一直进行调整即可。
代码如下：

   /**
     * 排序操作
     * @param data
     */
    private static void heapSort(String[] data){
        //每次循环都能取到一个最大值，该值为根节点
        for(int i=data.length-1;i>0;i--){
            String temp=data[0];
            data[0]=data[i];
            data[i]=temp;
            //每次调整都是从根节点开始i不断减小，保证前一次最大节点不会参与到调整堆
            maxHeap(data,i,0);
        }
    }

从代码可以看出来，每次调整都是从根节点开始，不断的缩小排序范围。继而达到把所有的节点全部排序。

完整代码如下：

package heapsort;

public class HeapSort{
    private static String[] sort=new String[]{"S","O","R","T","E","X","A","M","P","L",
            "E"};

    public static void main(String[] args){
        buildMaxHeap(sort);
        heapSort(sort);
        print(sort);
    }

    /**
     * 初始化构建堆
     * @param data
     */
    private static void buildMaxHeap(String[] data){
        //根据最后一个元素获取，开始调整的位置
        int startIndex=getParentIndex(data.length-1);
        //反复进行调整
        for(int i=startIndex;i>=0;i--){
            maxHeap(data,data.length,i);
        }
    }

    /**
     * 此调整为从上到下调整，直到节点超出范围
     * @param data
     * @param heapSize
     * @param index
     */
    private static void maxHeap(String[] data,int heapSize,int index){
        //取得当前节点的左右节点，当前节点为index
        int left=getChildLeftIndex(index);
        int right=getChildRightIndex(index);
        //对左右节点和当前节点进行比较
        int largest=index;
        if(left<heapSize&&data[index].compareTo(data[left])<0){
            largest=left;
        }
        if(right<heapSize&&data[largest].compareTo(data[right])<0){
            largest=right;
        }
        //交换位置
        if(largest!=index){
            String temp=data[index];
            data[index]=data[largest];
            data[largest]=temp;
            maxHeap(data,heapSize,largest);
        }
    }

    /**
     * 排序操作
     * @param data
     */
    private static void heapSort(String[] data){
        //每次循环都能取到一个最大值，该值为根节点
        for(int i=data.length-1;i>0;i--){
            String temp=data[0];
            data[0]=data[i];
            data[i]=temp;
            //每次调整都是从根节点开始i不断减小，保证前一次最大节点不会参与到调整堆
            maxHeap(data,i,0);
        }
    }

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

    /**
     * 获得左子节点的位置
     * @param current
     * @return
     */
    private static int getChildLeftIndex(int current){
        return(current<<1)+1;
    }

    /**
     * 获得右子节点的位置
     * @param current
     * @return
     */
    private static int getChildRightIndex(int current){
        return(current<<1)+2;
    }

    private static void print(String[] data){
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+",");
        }
    }

}

时间复杂度

堆排序是一种十分高效的排序算法，因为它的排序流程分三步，那么可以分别计算时间复杂度进行相加：
1.构建堆：
构建堆是从N/2处开始进行调整，每一次调整的时间复杂度为节点的深度H，那么N/2次调整则为O（H1）+O（H2）.....O(HnN/2)。由于H为常数，那么时间复杂度为O（N）
2.调整堆：
调整堆比较简单，由二叉堆具有堆序性质，那么调整堆的过程其实，就是堆的深度即lgN
3.堆排序
此过程是进行N-1次调整堆的操作，那么此过程的时间复杂为(N-1)lgN。
汇总后整体的时间复杂度为O（N+(N-1)*lgN） ~ O(NlgN)
可见堆排序的时间复杂度是比较低的，但是这种排序一般比较适合大数据集合的排序，因为大量使用了递归操作，那么在小数据集的情况下是十分消耗性能的，在小数据集的情况下最好使用插入、选择这种简单的排序算法，往往能起到更好的效果。
对TopK问题的优势：
堆排序另外一个比较好的特性就是TopK，因为堆排序是渐进排序，也就是说不是将所有的数据排序好后输出。这种特性也就决定了，在TopK场景往往能够有更好的表现。

空间复杂度

从上面程序可以看出来，我们并没有引入第二个存储元素，而每一次元素的交换仅仅依靠一个元素的存储空间，所以堆排序的空间复杂度为O（1）

参考：