最小堆的指定删除
大约 1 分钟
其实最小堆是可以指定删除某个节点的,包括最大堆。只要使用正确的方法
伪代码:
// 向下调整
if (末尾节点 key > 要删除的节点 key) {
//这里就使用尾换头的方法调整,只不过把所谓的 "头" 换成了指定节点
}
// 向上调整
else {
//这里的逻辑比尾换头简单的多,也是我们删除指定节点重要的地方,向上调整
因为我们要删除的节点 key > 尾节点 key,为了符合有序性的规则就必须将尾节点向上调整,调整方法也很简单:
1. 把尾节点转移到我们删除的节点位置
2. 循环遍历父节点,如果 key 比父节点小,那么父节点下移,当前节点上升。直到父节点 < 当前节点
// 注释:1. 尾节点能转移到删除节点位置就说明尾节点 key 比删除节点的所有子节点小,所以不必再调整子节点。
2. 当前节点的父节点也是删除节点的父节点,说明父节点 key < 删除节点,那么当前节点上升后也不需要重新调整下 移的原父节点
}