>[success] # 堆 ~~~ 1.堆 数据结构，也叫作二叉堆，是一种特殊的二叉树 2.它能高效、快 速地找出最大值和最小值，常被应用于优先队列 3.堆的定义： 3.1.它是一棵完全二叉树，完全二叉树要求，除了最后一层，其他层的节点个数都是满的， 最后一层的节点都靠左排列 3.2.堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。也可以说， 堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。对于每个节点的值都大于等于子树 中每个节点值的堆，我们叫做'大顶堆'。对于每个节点的值都小于等于子树中每个节点值的堆， 我们叫做'小顶堆'。 4.平均情况下，它的时间复杂度为 O(nlogn) ~~~  >[info] ## 堆的实现 ~~~ 1.首先堆是树的一种，树的实现有两种，一种是'链式存储法',需要更多的空间保存左右指针，一种是'顺序存储法' 在针对完全二叉树的形式用数组的方式，这样节省空间，'堆'的特殊性就是一个完全二叉树，因此用数组的作为 存储方式是最合适的 2.对应的数组关系 2.1 它的左侧子节点的位置是 2 * index + 1（如果位置可用） 2.2.它的右侧子节点的位置是 2 * index + 2（如果位置可用） 2.3.它的父节点位置是 index / 2 向上取整（如果位置可用）。 3.这里对二条做个说明，实际我们通过这些公式算的是，对应位置节点位置，举个例子，如图，左侧节点依次是 [2,4,6] 右侧 [3,5,7] ,带入公式2*index +1 想知道左侧树第一个位置的结点在大数组什么位置的时候，此时index为0 带入后等于1则左侧第一个节点在大数组角标为0的位置 ~~~ * 如图堆 和 数组存储对应关系