C++ BinaryHeap二叉堆如何实现deleteval()删除指定值函数

你当前的实现存在三个核心问题：

1. 直接调用vector::erase删除元素后没有维护堆的有序性质，会导致整个堆结构失效
2. 传入的val是要删除的目标值，不能直接作为vector的下标使用，会出现非法访问、删错元素的问题
3. 函数签名里的int p参数没有实际作用，可以直接删除

实现步骤 #

• 第一步：遍历存储堆的vector，找到目标值对应的下标位置，如果遍历完没有找到直接返回
• 第二步：将目标下标位置的元素和堆的最后一个元素交换，调用pop_back删除末尾的目标元素，避免移动整个数组的开销
• 第三步：对交换到原目标下标位置的元素执行堆调整：如果该元素比父节点优先级高就执行上滤，否则执行下滤，保证堆性质不被破坏
• 第四步：补充边界判断：堆为空、目标值不存在时直接返回，避免非法访问

示例实现 #

前提假设你的BinaryHeap已经实现了如下基础组件：

1. vector<Comparable> array 存储堆元素
2. percolateUp(int pos) 上滤函数，将pos位置的元素向上调整到合适位置
3. percolateDown(int pos) 下滤函数，将pos位置的元素向下调整到合适位置

template <typename Comparable>
void BinaryHeap<Comparable>::deleteVal(const Comparable &val)
{
    // 堆为空直接返回
    if (array.empty()) return;

    // 遍历找第一个匹配目标值的下标
    int targetPos = -1;
    for (int i = 0; i < array.size(); ++i) {
        if (array[i] == val) {
            targetPos = i;
            break;
        }
    }
    // 没找到目标值直接返回
    if (targetPos == -1) return;

    // 和最后一个元素交换，避免移动数组开销
    swap(array[targetPos], array.back());
    // 删除末尾的目标元素
    array.pop_back();

    // 删完已经空了无需调整
    if (array.empty()) return;

    // 小顶堆调整逻辑，如果是大顶堆把上滤的判断条件改成 > 即可
    if (targetPos == 0) {
        // 根节点直接下滤
        percolateDown(targetPos);
    } else if (array[targetPos] < array[(targetPos - 1) / 2]) {
        // 比父节点优先级高，执行上滤
        percolateUp(targetPos);
    } else {
        // 否则执行下滤
        percolateDown(targetPos);
    }
}

注意事项 #

• 上述实现默认只删除第一个匹配到的目标值，如果需要删除所有匹配值，把查找逻辑放到循环里重复执行直到找不到目标值为止
• 普通二叉堆按值删除的时间复杂度是O(n)，瓶颈在于遍历找元素的过程，如果需要更高的删除效率，可以额外维护一个unordered_map<Comparable, int>记录每个值对应的下标，但是要注意处理重复元素的冲突问题

内容的提问来源于stack exchange，提问作者codingisfun543