堆结构的解读

对于数据结构堆来说，堆事一种特定的数据结构，其与二叉树非常类似，但是又与二叉树有所不同，其不同点在于堆不需要左右指针指向孩子节点，而给定一个数组，将数组中的元素进行特定排序之后，就可以得到一个堆，如图是一个数组

添加图片注释，不超过 140 字（可选）

该数组的对应的堆如图：

添加图片注释，不超过 140 字（可选）

从其堆中可以知道，堆在结构上与二叉树几乎一模一样，图中显示的左右指针指向的孩子节点，将数组元素按照堆显示的层级进行排列即可，也就是将数组中的元素按照堆排列后就可以满足堆的性质。

添加图片注释，不超过 140 字（可选）

而在给定一个元素下标之后，就可以快速查找到该元素所对应的父节点和左右孩子节点，先假设元素下标的起始是1，当给定元素下标是为i的时候，我们使用操作parent(i)返回该元素所对应的父节点，left(i)返回该节点的左孩子节点，right（i）返回的是该节点的右孩子节点，这3种操作使用python实现如下：

def  parent(i):#返回给定下标元素对应的父节点下标return int((i+1)/2) - 1 #由于数组下标从0开始因此i要加1,同样原因返回结果要减1
def  left(i): #返回给定下标元素的左孩子下标return 2*(i+1) - 1
def  right(i): #返回给定下标元素的右孩子下标return 2*(i+1)

对于堆右大堆和小堆之分，大堆的特点是父节点的值大于等于孩子节点，小堆的特点是父节点的值小于等于孩子节点，于是在大堆中，在数组中值最大的元素一定在堆的顶部，而对应的位置也就是在数组的首位，同理，小堆而言，值最小的元素在堆的顶部，对应于数组就是最小值元素排在首位，可以向二叉树那样定义堆的高，由于每个节点最多只能包含两个子节点，因此对于n个元素的数组而言，它所对应的堆的高度就是lg(n)。