1.堆

堆是一种特殊的树，，只要满足这两点，它就是一个堆

堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。

其中第1个和第2个是大顶堆，第3个是小顶堆，第4个不是堆。除此之外，从图中还可以看出来，对于同一组数据，可以构建多种不同形态的堆。

2.实现一个堆

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

数组中下标为i的节点的左子节点，就是下标为i*2的节点，右子节点就是下标为i*2+1的节点，父节点就是下标为i/2的节点。

2.1 结构体定义及初始化

#define MaxSize 200
typedef int ElemType;
// 采用动态数组定义
// 注意：0号不存储元素
typedef struct
{
    ElemType* data;
    int length;
    int maxSize;
}HeapList;

// 注意：0号不存储元素
void initHeap(HeapList& L, int initSize)
{
    L.data = (ElemType*)malloc(sizeof(ElemType) * (initSize+1));
    L.length = initSize;
    L.maxSize = MaxSize;
}

2.2 插入元素

（1）堆化（ heapify）

不满足堆要求，就需要进行调整，让其重新满足堆的特性，这个过程就叫做堆化。

堆化两种，从下往上和从上往下。

堆化方法：顺着节点所在的路径，向上或者向下，对比，然后交换。

从下往上堆化：以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，就互换两个节点。

（2）堆化（插入）代码

// 从下往上堆化
void insertElemHeap(HeapList& L, ElemType data)
{
    if (L.length >= L.maxSize)
        return;
    // 将新插入数据放到最后
    L.length++;
    L.data[L.length] = data;
    // 自下往上堆化
    // 让新插入的结点与父节点比对大小，
    // 如果不满足子结点小于等于父结点的大小关系，就互换两个结点
    int i = L.length;
    while (i / 2 > 0 && L.data[i] > L.data[i / 2])
    {
        // 交换两个元素
        ElemType tmpElem = L.data[i];
        L.data[i] = L.data[i / 2];
        L.data[i / 2] = tmpElem;
        // 更新i下标
        i = i / 2;
    }
}

2.3 删除堆顶元素

任何节点的值都大于等于（或小于等于）子树节点的值，可以发现，堆顶元素存储的就是堆中数据的最大值或者最小值。

（1）数组空洞

当删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后再迭代地删除第二大节点，以此类推，直到叶子节点被删除。

（2）从上往下堆化

把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。
对于不满足父子节点大小关系的，互换两个节点，
并且重复进行这个过程，直到父子节点之间满足大小关系为止。

（3）代码

// 从上往下堆化,从标号为k的元素开始堆化
void heapify(HeapList& L, int k, int len)
{
    while (true)
    {
        // 寻找父结点的两个子结点中最大的一个
        int maxPos = k;
        if (k * 2 <= len && L.data[k] < L.data[2 * k])
            maxPos = k * 2;
        if (k * 2 + 1 <= len && L.data[maxPos] < L.data[2 * k + 1])
            maxPos = k * 2 + 1;
        // 若子结点比自己都小，父结点就是最大的
        if (maxPos == k)
            break;
        // 交换元素
        ElemType tmpElem = L.data[k];
        L.data[k] = L.data[maxPos];
        L.data[maxPos] = tmpElem;
        // 更新
        k = maxPos;
    }
}

void removeHeapTopElem(HeapList& L, ElemType& elem)
{
    if (L.length == 0)
        return;
    elem = L.data[1];
    L.data[1] = L.data[L.length];
    L.length--;
    heapify(L, 1, L.length);
}

3.堆排序

可以把堆排序的过程大致分解成两个大的步骤， 建堆和排序。

3.1 建堆

首先将数组原地建成一个堆。所谓“原地”就是，不借助另一个数组，就在原数组上操作。

是从后往前处理数组，并且每个数据都是从上往下堆化。

（）代码

// 从数组，原地建堆
void buildHeap(HeapList& L)
{
    for (int i = L.length / 2; i >= 1; i--)
    {
        heapify(L, i, L.length);
    }
}

3.2 排序

（1）步骤

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。
数组中的第一个元素就是堆顶，也就是最大的元素。
把它跟最后一个元素交换，那最大元素就放到了下标为n的位置。

（2）代码

void heapSort(HeapList& L)
{
    // 建立大顶堆
    buildHeap(L);
    printSqList(L);
    // 排序
    int tmpElem = 0;
    for (int i = L.length; i > 1; i--)
    {
        tmpElem = L.data[i];
        L.data[i] = L.data[1];
        L.data[1] = tmpElem;

        heapify(L, 1, i - 1);
    }
}

（3）复杂度

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是O(n)，排序过程的时间复杂度是O(nlog n)，所以，堆排序整体的时间复杂度是O(nlog n)。
堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

1.堆