数据结构笔记（树->堆）

堆(heap)：
结构性：用数组表示的完全二叉树
有序性：任一结点的关键字是其子树所有结点的最大值（最小值），从根结点到任一结点路径上的结点序列都是有序的
最大值：最大堆(MaxHeap)大顶堆
最小值：最小堆(MinHeap)小顶堆

堆(最大堆)的插入：
新元素插入到完全二叉树的下一位，如果新元素大于其父结点，则交换位置，直到其小于其父结点。O(logN)

堆(最大堆)的删除：
删除根结点，将树的最后一个结点替换为根，将新的根结点与它的左右子树的根节点比较大小，如果根节点小于左右子树的根节点，与两者中的较大者交换位置，直到其大于左右子树的根结点

堆(最大堆)的建立：
1、将N个元素相继插入到初始为空的最大堆中，O(NlogN)
2、O(N)
1、将N个元素按输入顺序存入，先满足完全二叉树的结构特性
2、调整各结点位置，以满足最大堆的有序特性（最大调整次数为各个结点的高度和）