堆排序

时间复杂度及空间复杂度
- 排序的时间复杂度：O(nlogn)
- 插入，删除的时间复杂度: O(logn)
- 建堆时间复杂度:O(n)
- 将大根堆转换为小根堆时间复杂度O(n),本质就是重新建堆
- 空间复杂度: O(1)

【拓展】何为线性时间复杂度：
如果一个算法的时间复杂度可以表示为T(n)=O(n)，其中n是输入规模，那么这个算法就具有线性时间复杂度。

算法思想
堆排序是完全二叉树，用数组顺序存储。当你把混乱的数字放入数组时，就已经默认已经建好一个完全二叉树了。

1. 第一步先从最后一个父节点开始到第一个父节点，维护整一颗二叉树。
2. 此时，数组中的0位置也就是树顶已经是最大（最小了）
3. 然后将树顶和数组中最后一个元素交换。
4. 此时从树顶开始重新维护
5. 重复3，4两个步骤，直到堆中只剩一个点呆在0的位置。
6. 排序成功

实现时需要注意的点
1. 实现维护方法，维护的方法是向下递归保证每个子树的根节点（最大/最小）。
2. 要设定一个nn代表堆上的点数，初始时等于n，每排好一个，则nn–。

code

void down(int i)    // i为需要维护的节点 , n为数组长度
{
    int largest = i;   // 默认父节点为最大
    int lson = 2 * i + 1;
    int rson = 2 * i + 2;

    if(lson < nn && q[largest] < q[lson])  largest = lson;
    if(rson < nn && q[largest] < q[rson])  largest = rson;

    if(largest != i)   // 如果发现父节点不是最大的
    {
        swap(q[i],q[largest]);
        down(largest);
    }
}

void heap(){
    nn = n;  //初始还没开始排序时，堆上的点数 = 全部点数。
    //建堆
    for(int i = (n-1-1)/2; i>= 0 ; i--)   // 从最后一个父节点开始遍历所以父节点，最后一个父节点为(n-1)/2。
        down(i);  // 遍历完所有循环之后，成功建成大根堆

    //排序
    for(int i = n - 1;i > 0 ; i--)
    {
        swap(q[i],q[0]);
        nn--;    // 排好一个，则堆上的点数减1
        down(0);
    }
}