二叉堆本质上是一种完全二叉树,它分为两个类型
大顶堆(最大堆)
最大堆的任何一个父节点的值,都大于或等于它左、右孩子节点的值
小顶堆(最小堆)
最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值
二叉堆的根节点叫作堆顶
最大堆和最小堆的特点决定了:最大堆的堆顶是整个堆中的最大元素;最小堆的堆顶是整个堆中的最小元素
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
从图中我们可以看到,数组中下标为 i 的节点的左子节点,就是下标为 i∗2 的节点,右子节点就是下标为 i∗2+1 的节点,父节点就是下标为 i/2 取整的节点