Heap sort

预备知识: Heap

堆排序，我们知道，堆的根结点值不是最大的(大顶堆)就是最小的(小顶堆)。

我们将一个无序序列调整为堆后，找到最大值或者最小值交换到序列的最前面或者是最后面，这样有序序列元素就增加一个，无序序列元素减少一个，对新的无序序列进行之前的操作，这样就实现了排序。

$\color{blue}{ 堆排序适用场景 }$: 关键字很多的情况。典型例子是从10000个关键字中选取前10个最小的（或最大的)。例如面试题中经常问到的海量数据问题就可以使用堆来做。

如果关键字比较少，则不推荐使用堆排序。

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

// 大顶堆调整
void adjustHeap(int a[], int p, int len)
{
    int curParent = a[p];  // 当前父亲结点
    int child = 2 * p + 1; // 找到当前结点左孩子，并让child指向左孩子
    while (child < len)
    {
        if (child + 1 < len && a[child] < a[child + 1])  // 如果右孩子结点值大于左孩子
            child++;                                     // child指向右孩子
        if (curParent < a[child]) // 孩子结点值大于父亲结点
        {
            a[p] = a[child];
            p = child;
            child = 2 * p + 1;
        }
        else
            break;
    }
    a[p] = curParent;
}

void heapSort(int a[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--) // 建立初始堆
        adjustHeap(a, i, len);
    for (int i = len - 1; i >= 0; i--)
    {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;

        adjustHeap(a, 0, i);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {5,10,7,34,23,58,2,55,35,45};
    cout << "Before sorting: " << endl;
    dbg(a);
    int len = sizeof(a) / sizeof(a[0]);
    heapSort(a, len);
    cout << "After sorting : " << endl;
    dbg(a);

    return 0;
}

运行结果如下:

时间复杂度: $\color{blue}{O(nlog_2n)}$。

分析: 完全二叉树的高度为$\lceil{log_2(n+1)}\rceil$, 其时间复杂度可以认为是$O(log_2n)$

空间复杂度$\color{blue}{O(1)}$: 使用了常数个辅助单元，故为$O(1)$.