ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

居然被heap难倒了

之前一直小看了heap觉得这个数据结构比较简单,等串讲的时候发现其实并不是的,居然为了heap的插入删除争论了很久.
这里特地记录一下,heap的性质是递归的父结点比子节点大,说白了就是一个优先队列.
push,pop都只要分别做一次向上调整和向下调整.

但之前我的知识体系好像调整要有一次down再一次up.
这是在真正调整的时候用的比如替换任意一个元素或者删除任意一个元素.
替换很好理解就是引入一个元素可能很大也可能很小,要么向上要么向下.
而我卡住的地方是删除,老是觉得把最后一个结点换上来应该是不用向上调整只要向下的,
因为这个定义是递归的,但是不是的,虽然在删除处i下面的子树可以,但是如果最后一个结点不在i的子树下面,比如另外一个i的兄弟子树下面,整棵树都比i小的话(这里指最小堆),那么其实情况和替换是类似的,所以任意删除和替换才是会把down up两个函数都写入,但都是只执行一次.