堆的实现
那么作为一种数据结构,它会有它自己的用途,下面分析堆是如何实现的
从上述的存储结构可以看出,实际上每一个数组都可以把它看成是一个二叉树,由于堆的特殊性,首要问题就是如何把一个数组中的数字排序满足堆的要求
向上调整算法
这个算法主要是用来进行堆中元素的插入,当插入一个元素,由于大堆/小堆,这个插入的元素可能不符合堆的要求,这时候就需要用到向上调整算法
该算法的应用场景就是当一个元素要插入一个堆时,可以用这个算法进行插入,使得后续的二叉树依旧是堆,前提是插入前的二叉树必须满足堆的要求
该算法的流程是这样的
首先,原本有一个堆,有一个新元素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掉了),那么接着就可以采用向下调整算法,让这个新的堆顶元素向下调整,这样就能实现目标
下面的图可以很好的解释这个原理
那么现在就要搞清楚什么是向下调整算法