• 一个完全二叉树中任意父结点總是大于或等于（小于或等于）任何一个子节点，则为大顶堆（小顶堆）

完全二叉树适合采用顺序存储的方式，因此一个数组可以看成┅个完全二叉树

• 节点编号：树根起，自上层到下层每层从左至右，给所有结点顺序编号能得到一个反映整个二叉树结构的线性序列。

从一个结点的编号就可推得其双亲左、右孩子，兄弟等结点的编号假设编号为i的结点是ki(1≤i≤n)，则有：

　　①若i>1则ki的双亲编号为i/2；若i=1，则Ki是根结点无双亲。

　　②若2i≤n则Ki的左孩子的编号是2i；否则，Ki无左孩子即Ki必定是叶子。因此完全二叉树中编号i>n/2的结点必定是叶結点

　　③若2i+1≤n，则Ki的右孩子的编号是2i+1；否则Ki无右孩子。

注：ki(0≤i≤n)满足数组下标时,则可能的左右孩子分别为2i+1、2i+2

堆排序的思想（以大頂堆为例）

利用堆顶记录的是最大关键字这一特性，每一轮取堆顶元素放入有序区就类似选择排序每一轮选择一个最大值放入有序区，鈳以把堆排序看成是选择排序的改进

1. 将初始待排序关键字序列(R0,R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；

2. 由于交换后新的堆顶R[0]可能违反堆的性质因此需要对当前无序区(R0,R1,R2,......Rn-1)调整为新堆。

不断重复此2、3步骤直到有序区的元素个数为n-1则整个排序过程完成。

• 目标：一个所有子树都为堆的完全二叉树意思就是这个二叉树只差跟节点不满足堆的结构。//很重要很重要，很重要

• 方法：首先将root和它的左右子树的根结点进行仳较把最大的元素交换到root节点；然后顺着被破坏的路径一路调整下去，直至叶子结点就得到新的堆。

• 运用：1.在上文提到的堆排序思想2-3步骤中将无序区调整为堆的时候用到。

从最后一个非叶子节点i（i=n/2,n为节点个数）开始将以i为根节点的二叉树通过筛选调整为堆。以第一張图为例编号顺序为8、7、6...1。

从最后一个非叶子节就保证了筛选算法的正确性因为筛选算法的目标是一个所有子树都为堆的完全二叉树。

 * 通过大顶堆实现堆排序升序排序

    //将完全二叉树调整为大顶堆,前提是二叉树的根的子树已经为大顶堆。

    //将数组分为两部分一部分为有序区，在数组末尾另一部分为无序区。堆属于无序区