参考资料：
Chapter 6 Heapsort

比较性能的时候发现，堆排序的性能甚至要好于快速排序。

堆的建立时间复杂度为O(n)，从最后第一个非叶子节点为floor(length/2)到1，从这些根节点开始调整以这些节点作为根的子树。

排序的时候把最大的值甩到最后面去，然后堆里面去掉这个，然后调整第一个。

排序和堆的建立过程中最基础的操作就是调整某一个元素使得其所在位置满足堆的规则，也就是下面的heapedOne函数。

其他的要注意序号从1开始比较好，父母是n，左孩子是2n，右孩子是2n+1。
如果孩子是m，则父母是floor(m/2)。完全树第一个非叶子节点是floor(n/2)，也就是最后一个的父母。

java中Integer的比较((Comparable) list.get(lc)).compareTo(list.get(largest))>0)

代码如下：

inline void swap(ElemType *x,ElemType *y)//使用指针传递地址
{
    ElemType temp;
    temp=*x;
    *x=*y;
    *y=temp;
}

//这里不用递归实现，增加效率，递归实现请看函数MaxHeapify
void MaxHeapify2(ElemType Buff[],UINT32 len,UINT32 Index)
{
    Buff[0] = Buff[Index];

    for (UINT32 i=Index*2;i<=len;i*=2)
    {
        if (i<len&&Buff[i]<Buff[i+1])
        {
            i++;
        }

        if (Buff[0]>Buff[i])
        {
            break;
        }
        else
        {
            Buff[Index] = Buff[i];
            Index = i;
        }
    }
}

//调整以Index为根的子树为最大堆
void MaxHeapify(ElemType Buff[],UINT32 len,UINT32 Index)
{
    UINT32  leftChild = Index<<1,rightChild = leftChild+1,Largest = Index;

    if(leftChild<=len&&Buff[Largest]<Buff[leftChild])
    {
        Largest = leftChild;
    }

    if (rightChild<=len&&Buff[Largest]<Buff[rightChild])
    {
        Largest = rightChild;
    }

    if (Largest!=Index)
    {
        swap(Buff+Largest,Buff+Index);
        MaxHeapify(Buff,len,Largest);
    }
}

//自底向上
void BuildMaxHeap(ElemType Buff[],UINT32 len)
{
    for (int i=len/2;i>=1;i--)
    {
        MaxHeapify2(Buff,len,i);
    }
}

//
void HeapSort(ElemType Buff[],UINT32 len)
{
    BuildMaxHeap(Buff,len);

    for (UINT32 i=len;i>1;i--)
    {
        swap(Buff+1,Buff+i);
        MaxHeapify2(Buff,i-1,1);
    }
}

java版本

import org.w3c.dom.ls.LSOutput;

import java.net.CookieHandler;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Heap<T> {
    private ArrayList<T> list;
    private int size;

    public Heap(T[] list) {
        this.list = new ArrayList<>();

        // 序号为0的不存放数据
        this.list.add(list[0]);
        for (int i = 0; i < list.length; i++) {
            this.list.add(list[i]);
        }

        this.size = this.list.size() - 1;

        //建立堆结构，O(n)
        heaped();
    }

    private void heaped(){
        for(int i=lastNonLeaf(); i>0; i--){
            heapedOne(i);
        }
    }

    private void heapedOne(int node){
        int largest = node;
        int size = size();

        int lc = getLeftChild(node);
        if((lc<=size)&&(((Comparable) list.get(lc)).compareTo(list.get(largest))>0)){
            largest = lc;
        }

        int rc = getRightChild(node);
        if((rc<=size)&&(((Comparable) list.get(rc)).compareTo(list.get(largest))>0)){
            largest = rc;
        }

        if(largest!=node){
            Collections.swap(list, largest, node);
            heapedOne(largest);
        }
    }

    private int getLeftChild(int parent){
        return parent*2;
    }

    private int getRightChild(int parent){
        return parent*2+1;
    }

    private int lastNonLeaf(){
        return size()/2;
    }

    private int size(){
        return size;
    }

    public void print(){
        System.out.println(list);
    }

    private List<T> sort(){
        int size = size();
        for(int i=0;i<size;i++){
            Collections.swap(list, this.size, 1);
            this.size -= 1;
            heapedOne(1);
        }

        return list.subList(1, list.size());
    }

    //要先注释掉构造函数里面的heaped函数
    public static void testHeapOne(){
        Integer[] list = new Integer[]{1,3,2,4,5,6,7,8,9,10};
        Heap<Integer> heap = new Heap(list);
        heap.heapedOne(5);
        heap.print();
        heap.heapedOne(4);
        heap.print();
        heap.heapedOne(3);
        heap.print();
        heap.heapedOne(2);
        heap.print();
        heap.heapedOne(1);
        heap.print();
    }

    //要先注释掉构造函数里面的heapd函数
    public static void testHeaped(){
        Integer[] list = new Integer[]{1,3,2,4,5,6,7,8,9,10};
        Heap<Integer> heap = new Heap(list);
        heap.print();
    }

    public static void testSort(){
        Integer[] list = new Integer[]{1,3,2,4,5,6,7,8,9,10};
        Heap<Integer> heap = new Heap(list);
        System.out.println(heap.sort());
    }
}