数据结构-在堆中插入或删除新元素

 目录

在堆中插入新元素

在堆中删除元素

知识回顾 

---

在堆中插入新元素

首先插入13（这里我们依据的是小根堆原则，遇到大根堆也是类似的）

（1）将新元素放到队列的队尾，在完全二叉树里面显示的是堆底

如下图是插入13的位置显示

 

 

 （2）对于小根堆，新元素和他的父节点对比，若新元素比父节点更小，则交换，让小元素一路上升

13小于32，所以13上升，和32交换，得到如图

此时对比第一次

 

13小于17接着交换，13上升

此时对比第二次

 

 

 13和父节点09对比，比其大，停止上升

此时对比第三次

在插入一个新元素46，放入堆底，数组的末尾

 

 

 新结点46和父结点对比，发现比45大，已经满足小根堆，不用交换

此时对比一次

 

在堆中删除元素

假设删除13

 

 

删除13后，将数组里面最后一个元素（即完全二叉树里面的堆底元素）放入到删除元素后的空缺位置） 

如图显示

 

 放入后的效果如下图所示：

 

根据小根堆，在完全二叉树里面看，这个堆底元素46和孩子对比，

孩子17和45对比一次，判断更小的元素是17

然后46和它更小的孩子元素17对比

所以第一趟对比关键字2次

如果46比其大，让这个46元素下坠，让其符合小根堆

所以46和17交换，如下图：

 

接着对比，根据小根堆，在完全二叉树里面看，这个堆底元素46和孩子对比

孩子53和32对比一次，判断更小的元素是32

然后46和它更小的孩子元素对比

所以第二趟对比关键字2次

如果46比其大，让这个46元素下坠，让其符合小根堆

所以46和32交换，如下图：

 

 

综上这里一共对比关键字的次数=4

在堆中删除元素需要注意对比关键字次数

孩子之间要对比一次，判断出来哪个更小，然后需要移动的元素再和更小元素对比，依次类推

 

 

 

 

在删除65 结点

同样堆底元素放入到删除的空缺位置，如下图所示

 

还是在完全二叉树里面比较大小，此时孩子之间对比78和87，更小的是78，然后堆底元素46和更小元素78对比，比其小，满足小根堆，所以一趟完成 

对比关键字次数=2次 

 

 

知识回顾