8.4.2_2堆的插入删除

在堆中插入新元素：

 如下所示要在小根堆里插入元素13，首先把新元素13放到表尾，逻辑视角的小顶堆的堆底，小根堆要求每个根节点的值<=左右子树节点的值，插入13后，让新元素和父节点相比较，新元素更小则让新元素和父节点互换，即破坏小根堆特性需要调整。先找新元素的父节点，13插入到编号为9的位置，13的父节点根据完全二叉树特性i/2向下取整，9/2向下取整=4号位32的位置，13>32(比较1次)，新元素更小破坏小顶堆特性让新元素13和父节点32互换，交换了之后当前父节点4号位还要继续和上一层父节点对比，因为更小的元素替换了父节点值可能导致上一层父节点元素又<新元素，则4号位的父节点为4/2=2号位17,13<17(比较2次)，则破坏小顶堆特性，让新元素和父节点交换，交换了之后继续向上一层父节点对比，上一层父节点2/2=1号位09,13>09(比较3次)则不用交换

 上同。如下所示要在小根堆里插入元素46，首先把新元素46放到表尾即10号位，逻辑视角的小顶堆的堆底。先找新元素的父节点，46的父节点根据完全二叉树特性i/2向下取整，10/2向下取整=5号位45的位置，45<46(比较1次)，新元素>父节点不用互换，新元素上升不了，插入结束。

在堆中删除元素：

 要在小根堆里删除元素，删除该元素所在位置就为空了，让堆底元素补上，然后一般会破坏小根堆特性(因为一般堆底元素会比删除的元素大吧，补上之后的元素可能>被删除元素所在位置的左右子树节点值，所以要让值大的元素下坠在下边)，所以让补上的元素下坠调整，直到无法下坠为止，恢复小根堆特性(根节点值<=左右子树节点值)。

如下在小根堆里删除元素13,13所在位置元素为空了，让堆底元素46补上。删除元素13所在位置为2号位，2号位左右子树为4号位17和5号位45选更小的4号位17(比较1次)，46和17比较根节点46>17交换(比较2次)，此时46在4号位继续下坠，4号位左右子树为8号位53和9号位32选更小的9号位32(比较3次)，46和32比较根节点46>32交换(比较4次)，此时46在9号位继续下坠，9号位左右子树为18号位和19号位>len=9，即9号位没有子树了下坠不了了，删除调整结束。

如下在小根堆里删除3号位元素65,13所在位置元素为空了，让堆底元素46补上。删除元素65所在位置为3号位，3号位左右子树为6号位78和7号位87选更小的4号位78(比较1次)，46和78比较46作为根节点更小符合小顶堆特性不交换(比较2次)，下坠不了了，删除结束。 

 知识回顾：

。。。。。。。。。。。。。。。。