跳至主要內容

最小堆的指定删除

muzzik大约 1 分钟笔记排序算法C++最小堆

其实最小堆是可以指定删除某个节点的,包括最大堆。只要使用正确的方法

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

📣 觉得很赞?分享给你的朋友吧!