数据结构 —— 堆_堆条件

作者：weixin_40725706 | 2024-06-26 01:49:32

踩

堆条件

堆

“堆”（Heap），实际上就是一种特殊的树。

什么样的树才是堆？需要满足两个条件

一、堆是一个完全二叉树；

二、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值（也可以说是其左右节点的值）。

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

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

如图，1和2就是大顶堆，3是小顶堆，4不是堆，因为4不是一个完全二叉树

因为堆是一棵完全二叉树，完全二叉树比较适合用数组来存储。

因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

用数组来存储完全二叉树是非常节省存储空间的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/758018