数据结构--无序的完全二叉树转为堆

无序的完全二叉树转为堆。

这里以转为最大堆为例：

首先要知道sift down下沉操作：下沉某个节点，即把该节点与它的两个子节点，共3个节点中值最大的结点选出来作为这三个节点中的父节点。并且，下沉后，被下沉的结点及其子节点还要进行下沉操作，直到不需要下沉为止，这是为了避免下沉后节点破坏了已经建立好的堆结构。

下沉操作举个例子：

如图：

上面这张图，28和62不需要下沉，只要下沉15节点后这个堆就可以构建完成了。

当15下沉后，15是与28节点交换位置，此时28变为该堆的根节点。

交换完后，检测到15及其两个子节点16和19不能构成大顶堆结构，所以需要对15再进行下沉操作.....

如果15下沉之后与子节点又不能构成大顶堆结构，那一直往下下沉.....

 

该完全二叉树的最后一层非叶子节点，从下往上，从右往左开始进行下沉sift down操作（

如图：

1.从值为17的节点开始下沉，然后下沉的结点按顺序为：41，28，15....