堆的概念和代码实现

1. 堆的概念和性质

什么是堆：

堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆的性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一棵完全二叉树。

现实中我们通常把堆使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。

2.堆的实现

定义堆

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* _a;
    int _size;
    int _capacity;
}Heap;

主函数

int main() {
    Heap* hp;
    hp = (Heap*)malloc(sizeof(Heap));
    int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7  };
    HeapCreate(hp, a, sizeof(a) / sizeof(a[0])); //创建堆
    HeapPrint(hp);                               //打印堆
    HeapPush(hp, 10);                            //在堆的尾部插入一个10
    HeapPrint(hp);
    HeapPop(hp);                               //堆的删除
    HeapPrint(hp);
    HPDataType tmp = HeapTop(hp);               //获取堆顶元素
    printf("%d\n", tmp);
    printf("%d\n", HeapSize(hp));               //打印堆元素个数
    printf("%d\n", HeapEmpty(hp));              //判断堆是否为空
    return 0;
}

向下调整算法

以这个二叉树为例，如何将它调整成小堆呢？

可以们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

调整步骤如下：

void AjustDown(HPDataType* a, int parent, int n)               //堆向下调整算法
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选出左右孩子中大的那一个，我这样写是为了后面建大堆方便排序，也可以选出左右孩子中小的那一个建小堆
        if (child + 1 < n && a[child] < a[child + 1])
        {
            child++;
        }
        //如果大的孩子比父亲还大就交换，继续往下调整
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

后面的代码都是以建大堆为例

堆的创建

如果这个数组是无序的，不是大堆也不是小堆，那如何建立一个大堆呢？根的左右子树不是大堆或者小堆就不能用向下调整算法，就需要从第一个非叶子节点向下调整，然后从第二个非叶子节点开始向下调整成大堆，通过自下而上进行向下调整，一直调到根节点为止。

void HeapCreate(Heap* hp, HPDataType* a, int n)              //堆的创建
{
    assert(hp);
    hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if (hp->_a == NULL)
    {
        perror("Heap::malloc");
        exit(-1);
    }
    memcpy(hp->_a, a, sizeof(HPDataType) * n);
    //建堆，size-1表示最一个孩子，size-2就找到了这个孩子的父亲
    for (int i = (n - 2) / 2; i >= 0; i--)
    {
        AjustDown(hp->_a, i, n);
    }
    hp->_size = n;
    hp->_capacity = n;
}

堆的插入

这里的插入是从堆的尾部插入，如果是一个大堆，然后尾部插入了一个非常小的值，那就不是大堆结构了，就需要进行向上调整，因为只是这一个数无序，其它元素都符合大堆结构，所以不需要从非叶子节点开始每个都向下调整。向上调整算法后面会给出。

void HeapPush(Heap* hp, HPDataType x)            //堆的插入
{
    assert(hp);
  //如果容量满了，就进行扩容
    if (hp->_size == hp->_capacity)
    {
        int newcapacity = hp->_capacity * 2;
        HPDataType* p = (HPDataType*)realloc(hp->_a, sizeof(HPDataType*) * newcapacity);
        if (p == NULL)
        {
            perror("Heap::realloc");
            exit(-1);
        }
        hp->_a = p;
        hp->_capacity = newcapacity;
    }
    hp->_a[hp->_size] = x;
    hp->_size++;
    AjustUp(hp->_a, hp->_size - 1, hp->_size);
}

向上调整算法

void AjustUp(HPDataType* a, int child, int n)             //向上调整算法
{
    int parent = (child - 1) / 2;
    //当child=0时就不需要调整了，不能用parent>=0作为判断条件，因为parent永远都不会小于0
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

堆的删除

这里的删除是指删除堆顶的数据，如果直接删除堆顶数据，那么大堆的结构乱了，还得重新再建大堆，太麻烦了，直接让堆顶数据和堆尾数据进行交换就可以，然后再进行一次向下调整即可。

void HeapPop(Heap* hp)                //堆的删除（删除堆顶）
{
    assert(hp);
    assert(!HeapEmpty(hp));
    //堆顶数据和堆尾数据交换
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    //如果交换过来的堆尾部数据太小，还需要向下调整成大堆
    AjustDown(hp->_a, 0, hp->_size);
}

获取堆顶元素

HPDataType HeapTop(Heap* hp)          //取堆顶的数据
{
    assert(hp);
    assert(!HeapEmpty(hp));
    return hp->_a[0];
}

堆的判空

bool HeapEmpty(Heap* hp)       //堆的判空
{
    assert(hp);
    return hp->_size == 0;
}

堆内元素个数

int HeapSize(Heap* hp)          //堆的数据个数
{
    assert(hp);
    return hp->_size;
}

打印堆内元素

void HeapPrint(Heap* hp)                         //堆的打印
{
    assert(hp);
    for (int i = 0; i < hp->_size; i++)
    {
        printf("%d ", hp->_a[i]);
    }
    printf("\n");
}

堆的销毁

void HeapDestory(Heap* hp)              //堆的销毁
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_size = hp->_capacity = 0;
}

建堆的时间复杂度推导

1.具有n个元素的平衡二叉树，树高为㏒n，我们设这个变量为h。

2.最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有2^(h-1)个元素，我们假定O(1)=1，那么这一层元素所需时间为2^(h-1) × 1。

3.由于是bottom-top建立堆，因此在调整上层元素的时候，并不需要同下层所有元素做比较，只需要同其中之一分支作比较，而作比较次数则是树的高度减去当前节点的高度。因此，第x层元素的计算量为2^(x) × (h-x)。
4.又以上通项公式可得知，构造树高为h的二叉堆的精确时间复杂度为：
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①

通过观察第四步得出的公式可知，该求和公式为等差数列和等比数列的乘积，因此用错位想减法求解，给公式左右两侧同时乘以2，可知：
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②

用②减去①可知： S =2^h × 1 - h +1 ③

将h = ㏒n 带入③，得出如下结论：S = n - logn +1 ≈ O(n)

3.堆的应用

堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1.建堆

    升序：建大堆

    降序：建小堆

2.利用堆删除思想来进行排序

    建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

问题：如果排升序建小堆会怎么样？

选出最小的数放到第一个位置，紧接着要选出次小的，次小的需要从左右孩子节点去选，这样一弄整棵树的关系全乱了，需要重新建堆才能选出次小的，建堆复杂度O(n)，那还不如直接遍历选数。

堆排序代码如下:

#include <stdio.h>
Swap(int* child, int* parent)
{
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}
void adjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
int main()
{
    int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    for (int i = (n - 2) / 2; i >= 0; i--)
    {
        adjustDown(a, n, i);
    }
    int end = n;
    while (end > 1)         //堆顶的数据和堆尾的数据进行交换，再向下调整
    {
        Swap(&a[0], &a[end - 1]);
        adjustDown(a, end-1, 0);
        end--;
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}