堆的实现

那么作为一种数据结构，它会有它自己的用途，下面分析堆是如何实现的

从上述的存储结构可以看出，实际上每一个数组都可以把它看成是一个二叉树，由于堆的特殊性，首要问题就是如何把一个数组中的数字排序满足堆的要求

向上调整算法

这个算法主要是用来进行堆中元素的插入，当插入一个元素，由于大堆/小堆，这个插入的元素可能不符合堆的要求，这时候就需要用到向上调整算法

该算法的应用场景就是当一个元素要插入一个堆时，可以用这个算法进行插入，使得后续的二叉树依旧是堆，前提是插入前的二叉树必须满足堆的要求

该算法的流程是这样的

首先，原本有一个堆，有一个新元素12要插入这个堆中，它的位置应该是作为15的孩子节点，但由于小堆的规则，12小于15，因此这里的12应该和15交换一下位置，接着12再和它的上一代比较，发现12小于10，满足小堆的规则，因此新堆就变成了右图所示的模样，至此就完成了堆的插入

这里不得不提的是，插入的元素要进行向上调整算法的最终目标是它的祖先，只要它和上一代之间不满足规则，就一直交换，直到它成为了它所在的这一代的祖先为止

一些实现过程中的技巧

知道了孩子节点的序号如何求父节点？

由于计算机除号的取整性，父亲节点 == ( 孩子节点-1 ) / 2

实现搭建堆

根据上面的两个步骤，我们就可以开始搭建堆了

首先是把数组插入到堆中

int main()
{
   
   
    HP hp;
    HeapInit(&hp);
    int arr[] = {
   
    9,8,6,5,43,2,1 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < sz; i++)
    {
   
   
        HeapPush(&hp, arr[i]);
    }

    return 0;
}

这里假设直接插入，没有进行任何算法调位，那么结果应该是这样的

如果用向上调整算法进行调整，后面的结果是这样的

void Swap(HPDataType* child, HPDataType* parent)
{
   
   
    HPDataType tmp;
    tmp = *child;
    *child = *parent;
    *parent = tmp;
}

void AdjustUp(HP* php, int child)
{
   
   
    int parent = (child - 1) / 2;
    while (child > 0)
    {
   
   
        if (php->a[child] < php->a[parent])
        {
   
   
            Swap(&php->a[child], &php->a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
   
   
            break;
        }
    }
}

void HeapPush(HP* php, HPDataType x)
{
   
   
    assert(php);

    if (php->size == php->capacity)
    {
   
   
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        php->a = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);
        if (php->a == NULL)
        {
   
   
            perror("malloc fail");
            return;
        }
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUp(php, php->size - 1);
}

从中可以看出，这样的算法是可以进行堆正确排序的，这样，堆就搭建起来了

下面我们进行堆相关的其他操作

实现出堆的操作

有数据入堆就少不了出堆，那么数据是如何出堆的？

首先要明确是谁出堆，初学可能会认为是堆的最后一个元素，事实上，这样的操作是没有意义的，因此这里出堆，出的是堆顶的元素，那么问题就来了，如何实现出堆的功能？

如果你不加思考去想，这个功能很简单，直接把数组后面的内容覆盖不就好了吗？事实上，这样的想法是错误的，原因在于覆盖后的堆还能维持原来的现状吗？原来的父子关系会变成兄弟关系，原来的兄弟关系也会因为少了一个元素而发生改变，这整个过程会有很大变化，因此，这里引入了第二个算法，向下调整算法

这个算法设计也是很巧妙，假设我们现在搭建的是小堆，那么堆顶的元素是最小元素，现在我们让堆顶这个最小元素和整个堆的最后一个元素互换位置，那么此时堆顶元素变成另外一个元素，但是堆的其他部分依旧符合小堆的规则(交换的原来的最小值堆顶就不计入堆中了，已经被pop掉了)，那么接着就可以采用向下调整算法，让这个新的堆顶元素向下调整，这样就能实现目标

下面的图可以很好的解释这个原理

那么现在就要搞清楚什么是向下调整算法