上次写到了快排，接着往下讲。O（nlogn）级别的算法除了上次说的快排，归并，还有推排序。今天从先推排序开始写。堆排序是堆的一个主要应用，要说清楚推排序就要先介绍堆，而且后面打算写一下计算时间复杂度（我自己算了一遍感觉挺有意思），所以堆排序可能会写的长一点。
说明：
1.如果你不清楚树，建议先了解一下树再往下看
2.本文是个人学习笔记，参考了算法导论和网上其他文章

一、二叉堆

1.定义

二叉堆是棵完全二叉树（后面会用到一些完全二叉树的性质），并且父结点的键值总是大于等于（叫最大堆）或小于等于（最小堆）子节点的键值。并且每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
因为二叉堆最常用，一般简称的堆就是指二叉堆。

最小堆

2.表示

一般是用数组表示，因为堆是完全二叉树，用数组储存不会浪费空间。上面这个堆可以表示为：

数组表示堆

左右孩子下标分别为2 * i + 1和2 * i + 2。
用Java写一个堆应该先声明堆类，定义各种成员变量和方法，写构造函数等等，由于我们这里主要为了写堆排序算法，所以下面就只介绍三个重要操作插入、删除、建堆，然后写三个函数。图解如下。

Paste_Image.png

3.插入节点

假设现在已经有了一个堆，插入一个新节点，步骤如下：

1. 堆的大小+1
2. 新节点放在堆的尾部（数组最后一个位置）
3. 从下至上（根）调整新节点位置，令其再次满足堆的定义（这个步骤叫堆化）

可以发现从这个新结点到它的父节点一直向上，到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数列的合适中。是不是和之前写的插入排序很像？其实代码写法也差不多，只是现在不需要依次往前遍历数组，只要一层一层往上遍历，所以一次插入的时间复杂度也从O（n）变得更快了。代码如下：

void insert(int[] A, int count, int data){
        int i,temp;
        i=count++;
        A[i]=data; 
        while(i!=0&&(i-1)/2>=0&&A[(i-1)/2]<data){
            temp=A[i];
            A[i]=A[(i-1)/2];
            A[(i-1)/2]=temp;
            i=(i-1)/2 
        }
    }

时间复杂度为O（logn），因为在最坏情况下，需要从最后一层出发，一直向上到根节点，遍历的次数就是树的高度。那么为什么树的高度h=logn？
这是因为堆是个完全二叉树。除了最底层，其他层都是满的，故它的节点个数n为2^h~2(h+1)-1，h表示树高。这就表明h<=logn<=h+1，由于h为整数，所以h=logn。

4.删除节点

堆只能删除根节点（最大或最小节点）。操作如下：

1. 根节点与最后一个节点交换并删除它（就是直接把最后一个节点赋值给根节点）
2. 从根节点开始向下堆化，令其再次满足堆的定义。

向下堆化和上面的向上堆化差不多，但是是和子节点中最大（最小）的比较，交换。调整时先在左右儿子结点中找最大的，如果父结点比这个最大的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。这个过程也叫"向下渗透"。

    int delete(int[] A, int count){
        if(count==-1)
            return -1;//当堆为空时，报错
        int data = A[0];
        A[0]=A[count--];
        down(int[] A, int count);
        return data;//返回删除的值
    }

  //向下堆化
    void down(int[] A,int count){
        int i =0;//从根节点开始
        int r,l;
        int maxson;
        for(l=2*i+1,r=2*i+2;;){
            if(r<=count){
                if(A[l]>A[r])
                    maxson=l;
                else
                    maxson=r;
            }
            else if(l<=count&&r>count)
                maxson=l;
            else if(l>count)
                break;
            if(A[maxson]>A[i]){
                int temp=A[i];
                A[i]=A[maxson];
                A[maxson]=temp;
                i=maxson;
            }
            else
                break;
        }
    }

复杂度同插入，原因也一样

5.建堆

建堆的一个简单思路是，将输入数据依次插入空堆中，这需要n次连续插入操作，最坏情况时间复杂度O（nlogn）。

不过建堆显然不用这么麻烦，看下面这种思路。叶子节点没有子节点，可以视作已经是满足条件的堆。从最后一非叶子节点开始向下堆化，直到根节点。观察发现最后一个非叶子节点就是最后一个节点的父节点。比如下面这个堆，按红色序号的顺序分别向下堆化。

void build(int[] A,int count){
        for(int i=(count-1)/2;i>0;i--){
            down(A,count,i);
        }

显然，这种方法效率更高。因为只对几乎一半的节点进行了堆化。而且下层节点数量远大于上层节点（下层节点数量是倍增的），向下堆化，下层节点交换次数少，向上堆化，下层节点交换次数多。计算后这种方法可以在时间O（n）内完成。具体计算方法后面再讲。

二、堆排序

堆排序思想是数组创建成堆，依次删除根结点（最大元素）并放入序列直到堆空。需要注意的是堆排序可以是原地的。具体做法看代码吧，主要就是删除根时的处理，和向下调整不要写成递归的。
注意：上面的代码直接手写没测试，可能有错。。。理解意思就行，下面这个代码跑过没问题。

package fuckingtest;

import java.util.*;

public class HeapSort {
    public int[] heapSort(int[] A, int n) {
        int count=n-1;
        build(A,count);
        for(;count>0;){
            int temp = A[0];
            A[0]=A[count--];
            down(A, count,0);
            A[count+1]=temp;
        }
        return A;
      
            
    }
    
    void build(int[] A,int count){
        for(int i=(count-1)/2;i>=0;i--){
            down(A,count,i);
            System.out.println(i);
        }
      
    }
    
    void down(int[] A,int count,int i){
        int r,l;
        int maxson=-1;
        for(;;){
            l=2*i+1;
            r=2*i+2;
            if(r<=count){
                if(A[l]>A[r])
                    maxson=l;
                else
                    maxson=r;
            }
            else if(l<=count&&r>count)
                maxson=l;
            else if(l>count)
                break;
            if(A[maxson]>A[i]){
                int temp=A[i];
                A[i]=A[maxson];
                A[maxson]=temp;
                i=maxson;
            }
            else
                break;
        }
    }
    
    public static void main(String[] args) {
        int[] r=new int[6];
        int[] a=new int[]{1,5,3,4,2,6};
        HeapSort h = new HeapSort();
        r = h.heapSort(a,6);
        for(int t:r){
            System.out.println(t);
        }
    }
      
}

性能：
时间复杂度最坏平均都是O（nlogn）。原因是建堆是线性时间，然后需要连续删除n次。额外空间复杂度O（1）（原地的）。是不稳定算法。虽然都是O（nlogn）级别算法，但由于快排常量系数更小，最好情况更快，所以快排效率更高。但堆排序的优势是它可以是原地的。

三、复杂度分析

单次插入，单次删除操作最坏情况时间复杂度O（logn）这个很好理解，那为什么建堆操作的时间复杂度是O（n）？我们接下来就具体计算一下。

为方便计算，考虑堆是满二叉树的情况（因为计算的是最坏情况，考虑满二叉树也没问题）。顺着刚才讲过的每层节点的交换次数想，我们计算所有节点在建堆过程中交换的次数和。

假设元素个数为n，树高h为㏒n。那么第x层的一个节点，其深度为x，高度为h-x，第x层总共有2^x个节点。

最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有2^{(h-1)个元素，我们假定O(1)=1，那么这一层元素所需时间为2}(h-1) × 1。倒数第二层最多只需要下调2次，顶点最多需要下调h次，而最后一层父节点共有2^{(h-1)个,倒数第二层公有2}(h-2),顶点只有1(2^0)个，

因此，可以总结出通项公式，第x层元素的计算量为2^(x) × (h-x)。
又以上通项公式可得知，构造树高为h的二叉堆的精确时间复杂度为：
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①

观察发现，这不就是高中时候学的数列问题吗！该求和公式为等差数列和等比数列的乘积，因此用错位相减发求解，给公式左右两侧同时乘以2，可知：
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②

用②减去①可知： S=2^h+2(h-1)+......+2^1+1-h ③

③式是个等比数列，根据等比数列公式（别告诉我连这个都忘了。。。）求得
S =2^h - h -1 ③

将h = ㏒n 带入③，S = n - ㏒n -1= O(n)

证明成功！

用这个方法，同样可以去计算n次连续插入或n次连续删除的时间复杂度。因为n次插入和n次删除道理是一样的，交换次数一样，可以看成互为逆过程，计算一个就行，我们这里计算n次插入，更好理解些。

最下层有2^h个节点，交换h次，总结出求和公式：
S=2^1*1+222+......+2^hh
同样用错位相减法，求得S=2^(h+1)*(h-1)+2=2n(logn-1)+2=O(nlogn)
这样建堆的时间复杂度和n次删除的时间复杂度就都清楚了。

再继续分析建堆过程，其实如果从上往下看，很像递归，而对这种问题，我们可以用分治法主定理来计算。
建堆算法是从最后一个非叶子结点开始下溯（向下堆化），也可以把建堆过程想成先对左子树建堆(T(n/2))，再对右子树建堆(T(n/2))，最后对根下溯(O(lg n))。
所以递推式是T(n) = 2*T(n/2) + O(lg n)
根据主定理可知，它的解是 T(n) = O(n)。

总结

显然，把这个问题看作递归形式，套主定理公式简单了许多。我们可以自然地想到，主定理公式本质上是不是其实就是把上面的数学推导总结成了公式，也就是说我们是不是也可以用上面的方法去证明主定理？

之前遇到复杂度分析，我总是简单记一下书上的结论，只是知其然不知其所以然。主定理也只是简单了解下，没有深入了解它的原理。其实许多问题，比如快排枢轴点为什么选择中间的最好这些都不是很理解。感觉以后不能偷懒，还是得真正把问题弄明白。

另外感觉网上大部分中文资料对复杂度的数学推导不够。比如之前搜跳表（skipList）的时候，大部分博客只讲了跳表的结构，一些基本操作和特性。对于随机的跳表节点高度为什么能证明出O(1)复杂度，几乎没有给出数学推导的。所以最好还是手边备一本经典算法书，并且最好习惯查英文资料