数据结构--无序的完全二叉树转为堆
无序的完全二叉树转为堆。
这里以转为最大堆为例:
首先要知道sift down下沉操作:下沉某个节点,即把该节点与它的两个子节点,共3个节点中值最大的结点选出来作为这三个节点中的父节点。并且,下沉后,被下沉的结点及其子节点还要进行下沉操作,直到不需要下沉为止,这是为了避免下沉后节点破坏了已经建立好的堆结构。
下沉操作举个例子:
如图:
上面这张图,28和62不需要下沉,只要下沉15节点后这个堆就可以构建完成了。
当15下沉后,15是与28节点交换位置,此时28变为该堆的根节点。
交换完后,检测到15及其两个子节点16和19不能构成大顶堆结构,所以需要对15再进行下沉操作.....
如果15下沉之后与子节点又不能构成大顶堆结构,那一直往下下沉.....
该完全二叉树的最后一层非叶子节点,从下往上,从右往左开始进行下沉sift down操作(
如图:
1.从值为17的节点开始下沉,然后下沉的结点按顺序为:41,28,15....