堆排序

一、堆结构

1. 堆的定义

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，
而它的两个子节点的位置分别为 2k 和 2k+1。

这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

int heap[maxN+1];
int N = 0;
bool isEmpty {return N==0;}
int size() {return N;}

2. 上浮和下沉操作

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

void swim(int k)
{
    while (k > 1 && heap[k/2]<heap[k])
    {
        swap(k/2, k);
        k = k/2;
    }
}

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，
应当与两个子节点中最大那个节点进行交换。

void sink(int k)
{
    while (2 * k <= N)
    {
        int j = 2 * k;
        if (j < N && heap[j]<heap[j+1])  //如果节点k有两个子节点，选出最大子节点
            j++;
        if (heap[k]>heap[j])    //如果最大子节点不大于节点k，下沉完成
            beak;
        swap(k, j); //如果最大子节点大于节点k，交换最大子节点和节点k，继续下沉
        k = j;
    }
}

3. 插入元素

将新元素放到数组末尾，然后上浮到合适位置

void insert(int v)
{
    heap[++N] = v;
    swim(N);
}

4. 删除堆顶元素

从数组顶端删除最大元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置

int delMax
{
    int max = heap[1];
    swap(1, N--);
    heap[N+1] = null;
    sink(1);
    return max;
}

二、堆排序

给定一个数组，将其使用堆排序进行排序。需要先使用sink函数将这个数组构造成最大堆，接下来每次讲堆顶的最大元素取下来与数组的最后一个元素交换，这时候最大堆的结构已经被破坏，将数组元素个数减一并且对新的堆顶元素调用sink函数使数组恢复最大堆，重复执行这个过程，直到所有元素都已排序。

1. 构建堆

无序数组建立堆最直接的方法就是从左到右遍历数组进行上浮操作。

一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为
根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要便利一半的元素即可。

2. 交换堆顶元素与最后一个元素

交换之后需要进行下沉操作维持堆的有序状态

3. 完整代码

void heap_sort(vector<int>& nums)
{
    int size = num.size()-1;
    for (int k = size/2; k >= 1; k--)
        sink(nums, k, N);
    while (N > 1)
    {
        swap(nums, 1, N--);
        sink(nums, 1, N);
    }
}
void sink(vector<int>& nums, int k, int N)
{
    while (2 * k <= N)
    {
        int j = 2 * k;
        if (j < N && heap[j]<heap[j+1])
            j++;
        if (heap[k]>heap[j])
            beak;
        swap(k, j);
        k = j;
    }
}

三、性能分析

堆高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为logN

堆排序：要对N个节点进行下沉操作，所以时间复杂度为NlogN

堆排序为原地排序，不需要额外空间