最近在恶补一些计算机基础内容，看到了堆排序，想想以前常说堆栈堆栈，但我竟然连堆有哪些应用都记不得了，所以，重温了堆排序后，我来给大家分享一下，希望能对大家有所帮助。（代码实现不采用伪代码，使用java实现，毕竟来看博客的都不想和看书一样把）

       首先，堆是一种数据结构，你可以把他看成一颗完全二叉树，如下图所示：圆圈上方的数字代表下标：他的特性就是：父结点的值要大于两个儿子结点的值。

        上图选自算法导论，下标从1开始，但我们写的时候，肯定是要按照从0开始的下标来写代码拉，这一点后面不会再特别说明了。

        虽然堆可以用数组表示，但堆和数组有所区别，主要是在于数组的长度（length）不一定等于堆的大小（heapSize）。heapSize <= length。下标大于heapSize但小于length的值都不属于堆结构。

        所以，在java里先新建一个类来表示堆：没有使用数组的原因是，java里数组初始化以后就不能再添加元素了，在讲解后面内容的时候会有所不方便。

public class Heap {

    private ArrayList<Integer> A;

    private int heapSize;

    public ArrayList<Integer> getA() {
        return A;
    }

    public void setA(ArrayList<Integer> a) {
        A = a;
    }

    public int getHeapSize() {
        return heapSize;
    }

    public void setHeapSize(int heapSize) {
        this.heapSize = heapSize;
    }
    
}

        很容易得知，结点i的左儿子右儿子或父结点的下标的计算函数

    int left(int i){
        return i * 2 + 1;
    }
    int right(int i){
        return i * 2 + 2;
    }
    int parent(int i){
        return (i - 1) / 2;
    }

      当儿子结点大于父节点的时候，就失去了最大堆的性质，所以在这个时候，我们只要把儿子结点和父结点交换，但是交换以后，被交换的父结点的儿子结点发生了变化，可能会继续违背最大堆这个性质，所以要递归调用这个算法。过程大致如下图所示：

对2号结点进行最大堆性质的保持

        要实现这个过程的代码如下：

    public void MaxHeapify(Heap heap, int i){
        int l = left(i);
        int r = right(i);
        int largest;
        if(l < heap.getHeapSize() && heap.getA().get(l) > heap.getA().get(i)){
            largest = l;
        }else{
            largest = i;
        }
        if(r < heap.getHeapSize() && heap.getA().get(r) > heap.getA().get(largest)){
            largest = r;
        }
        if(largest != i){
            int temp = heap.getA().get(i);
            heap.getA().set(i, heap.getA().get(largest));
            heap.getA().set(largest, temp);
        }else{
            return;
        }
        MaxHeapify(heap, largest);
    }

其实，这个算法是可以非递归实现的，可以提升效率：

    public void MaxHeapifyNoRecursive(Heap heap, int i){
        while(true){
            int l = left(i);
            int r = right(i);
            int heapSize = heap.getHeapSize();
            ArrayList<Integer> A = heap.getA();
            int largest;
            if(l < heapSize && A.get(l) > A.get(i)){
                largest = l;
            }else{
                largest = i;
            }
            if(r < heapSize && A.get(r) > A.get(largest)){
                largest = r;
            }
            if(largest != i){
                int temp = A.get(i);
                A.set(i, heap.getA().get(largest));
                A.set(largest, temp);
            }else{
                return;
            }
            i = largest;
        }
    }

        有了上述的算法，我们就可以进行建堆操作了，建堆的过程很简单，从下标heapSize - 1开始，对每个结点都执行MaxHeapify就行了，但是叶子结点由于没有子结点，所以只需要从（heapSize - 1）/2开始，对每个结点都执行MaxHeapify就行了

    public void BuildMaxHeap(Heap heap){
        int heapsize = heap.getHeapSize();
        for(int i = (heapsize - 1) / 2; i >= 0; i--){
            MaxHeapify(heap, i);
        }
    }

接下来，就是堆排序算法了。

先用BuildMaxHeap把输入的数组A构造成最大堆。然后，把下标heapSize - 1的元素和下标为0的元素对换，通过减小heapSize，让下标为heapSize - 1的元素从堆中剔除，再调用MaxHeapify（heap, 0）即可保证最大堆的性质。重复这个过程，直到堆中只剩下一个元素。

    public void HeapSort(Heap heap){
        BuildMaxHeap(heap);
        int length = heap.getA().size(), heapSize = heap.getHeapSize();
        for(int i = length - 1; i > 0; i--){
            int temp = heap.getA().get(i);
            heap.getA().set(i, heap.getA().get(0));
            heap.getA().set(0, temp);
            heap.setHeapSize(--heapSize);
            MaxHeapify(heap, 0);
        }
    }

这样堆排序算法就算完成了，复杂度仅为O(nlg(n))，但是，其实快速排序往往优于它，虽然复杂度和它一样。所以下一篇博客我会写堆的另一个应用——优先级队列。

如果对代码有疑惑可以看我的github源码，上面有所有方法的单元测试：https://github.com/qjkobe/IntroductionToAlgorithms

如果发现问题，请立刻告诉我。我可不想误人子弟