堆的创建和说明

文章目录

前言

我们已经知道了二叉树的样子，但是一般的二叉树是没有什么意义的，所以我们会使用一些特殊的二叉树来进行实现，而堆就为特殊的二叉树来表示的。

---

一、堆是什么？

堆是一种特殊的二叉树，由完全二叉树来表示，分为小堆和大堆的表现形式，小堆的表现形式为父节点比孩子节点要小，下面的根节点同样满足这个条件，大堆与之相反，父节点要比孩子节点大，根节点同样满足条件。

小堆：

大堆： 

二、使用步骤

1.创建二叉树

创建堆我们首先需要创建一个二叉树，我们可以使用数组的形式来表示二叉树，逻辑结构上我们将数组看为二叉树的形式，物理结构上还为数组，我们现在需要将其修改为堆。

2.修改为堆

我们需要得知其的父节点个子节点，可以举例为第一个节点为父节点下标为0，子节点的下标为1和2。当父节点下标为1时，子节点下标3和4。由此可以推出公式，

父节点=(子节点-1)/2

子节点=父节点*2+1

通过这两个公式我们就可以试着将二叉树修改为堆。

3.向上调整

我们建造一个小堆要使父节点比子节点都要小，我们可以通过子节点和父节点进行对比，如果子节点更小的话就将其进行交换，我们可以通过公式由子节点来找到父节点来进行实现，结束条件就为子节点小于或等于0时。

void Adjiustup(typedata* ps, int child)
{int parent = (child - 1) / 2;while (child > 0){if (ps[child] < ps[parent]){Swap(&ps[child], &ps[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

结果实现 

运行结果如图所示，成功创建小堆，如果要创建大堆的话，只需要修改子节点和父节点的比较条件即可。

---

总结

一般的二叉树是没有什么意义的，这个堆我们可以根据其的特性进行一些有意义的事情，希望我的这篇文章对您有所帮助，如有错误，欢迎指出。