堆的标记删除：简单实现对给定 key 的删除操作

字数统计: 1.6k字 | 阅读时长: 7分

2020-11-04

摘要: 带标记删除的堆

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们借鉴 GC 中的标记删除算法，在堆的元素中加上标记删除，实现对堆中元素的动态删除。

我们给出代码模板，最后用 239. 滑动窗口最大值、480. 滑动窗口中位数两道题做代码测试，速度比直接哈希索引堆好很多。

$0 场景

一般的堆不支持按 key 删除。

现实中这种需求是常见的，例如进程调度的时候，进程 ID 和进程优先级在一个堆中维护。直接删除某个进程 ID 是很合理的需求。

为了实现按 key 删除，内部直接加哈希索引形成索引堆是性能不一定好但很直接的一种方式。参考哈希索引堆。

另外一种办法类似于 GC 中常见的标记-清除算法，是基于惰性更新的思想，先标记删除，访问到该数据的时候才真正删除。

算法：标记删除 + 惰性更新

增加删除标记，使得给堆提供 key 之后，可以标记该 key 已经被删除，以后若访问到该 key 再真正删除。这种方式为惰性更新的思想。

深入参考：GC 标记 - 清除算法。

$1 带标记删除的堆

数据结构设计

label 为标记 mapping[key] := key 实际的频数，当删 key 时，--mapping[key] 就相当于做了标记。data 为数据。

_size 表示堆中维护的元素个数，即堆当前持有的数据是 data[1.._size]，_delete 表示当前堆中被标记删除但是尚未真正删除的元素个数。

vector<int> data; // keys
int _size;
int _delete;
unordered_map<int, int> label; // key -> cnts

堆的基本操作

调整堆 push_up(i), push_down(i)
插入 push(key)
查询最值 top()
弹出堆顶 pop()
建堆 build(nums)
扩容 dilatation()

基本没有变化，只是注意维护 _delete 以及 label。插入的时候 ++label[key]，查询最值的时候先将堆顶已标记的 key (label[key] 为 0 表示堆中已经不持有 key 了) 执行真正删除，每删一个, _delete 自减 1。

标记删除

若 label 中有 key 的记录，将其自减 1，并将 _delete 自增 1，即为做了删除标记。(_size不变)

后续当 top() 和 pop() 的时候有可能依然可以正常访问该 key，因为 label[key] 有可能没有减到 0。

当堆持有的所有 key 都标记删除了，堆头就不能访问该元素了，再删除该 key 也相应地会直接返回。

void remove(int key)
{
    if(label.count(key) == 0)
        return;
    --label[key];
    if(label[key] == 0)
        label.erase(key);
    ++_delete;
}

完整代码 (C++，模板)

class LabelMaxHeap
{
public:
    LabelMaxHeap()
    {
        data.assign(1, -1);
        _size = 0;
        _delete = 0;
    }

    void build(const vector<int>& nums)
    {
        data.clear();
        int n = nums.size();
        data.assign(n + 1, 0);
        data[0] = -1;
        for(int i = 0; i < n; ++i)
        {
            data[i + 1] = nums[i];
            ++label[data[i + 1]];
        }
        _size = n;
        for(int i = n; i >= 1; --i)
            push_down(i);
    }

    int top()
    {
        if(empty())
            return -1;
        while(label.count(data[1]) == 0)
        {
            data[1] = data[_size--];
            --_delete;
            push_down(1);
        }
        return data[1];
    }

    int pop()
    {
        if(empty())
            return -1;
        int ans = top();
        --label[ans];
        if(label[ans] == 0)
            label.erase(ans);
        data[1] = data[_size--];
        push_down(1);
        return ans;
    }

    void push(int key)
    {
        if(_size + 1 >= (int)data.size())
            dilatation();
        ++label[key];
        data[++_size] = key;
        push_up(_size);
    }

    void remove(int key)
    {
        if(label.count(key) == 0)
            return;
        --label[key];
        if(label[key] == 0)
            label.erase(key);
        ++_delete;
    }

    int size()
    {
        return _size - _delete;
    }

    bool empty()
    {
        return size() == 0;
    }

private:
    vector<int> data; // keys
    int _size;
    int _delete;
    unordered_map<int, int> label; // key -> cnts

    void dilatation()
    {
        vector<int> tmp_data((_size + 1) * 2 + 1);
        tmp_data[0] = 1;
        for(int i = 1; i <= _size; ++i)
            tmp_data[i] = data[i];
        data.swap(tmp_data);
    }

    void push_up(int i)
    {
        if(i > _size) return;
        while(i / 2 > 0 && data[i / 2] < data[i])
        {
            swap(data[i], data[i / 2]);
            i /= 2;
        }
    }

    void push_down(int i)
    {
        int ori = i, left = i * 2, right = i * 2 + 1;
        if(left <= _size && data[left] > data[ori])
            ori = left;
        if(right <= _size && data[right] > data[ori])
            ori = right;
        if(ori != i)
        {
            swap(data[i], data[ori]);
            push_down(ori);
        }
    }
};

$2 代码测试

239. 滑动窗口最大值

本题最好的解法是单调队列，如果想用堆的话，必须解决滑窗左端点 nums[i - 1] 如何删除的问题，标记删除是一个思路。

注：哈希索引堆过不了的 N = 1e5, K = 1e4 的数据带删除标记的堆可以过，最终 1184ms 通过。(最优解单调队列 430ms)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        cout << nums.size() << endl;
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        LabelMaxHeap heap;
        heap.build(vector<int>(nums.begin(), nums.begin() + k));
        vector<int> result;
        result.push_back(heap.top());
        for(int i = k; i < n; ++i)
        {
            heap.remove(nums[i - k]);
            heap.push(nums[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};

480. 滑动窗口中位数

注：直接加哈希索引的对顶堆是 1140 ms，带标记删除的对顶堆为 132ms。

本题在标记删除的基础上还要结合对顶堆，算法原理参考力扣480-滑动窗口中位数。

class LabelOppositeHeap
{
public:
    LabelOppositeHeap(){}

    void insert(int x)
    {
        if(heap_left.empty() || x <= heap_left.top())
            heap_left.push(x);
        else
            heap_right.push(x);
        balance();
    }

    double query()
    {
        double left = heap_left.top();
        if(heap_left.size() == heap_right.size() + 1)
            return left;
        double right = heap_right.top();
        return ((double)left + (double)right) / 2;
    }

    void index_delete(int x)
    {
        if(!heap_left.empty() && x <= heap_left.top())
            heap_left.remove(x);
        else
            heap_right.remove(x);
        balance();
    }

private:
    LabelMaxHeap heap_left;
    LabelMinHeap heap_right;

    void balance()
    {
        if(heap_left.size() > heap_right.size() + 1)
        {
            heap_right.push(heap_left.top());
            heap_left.pop();
        }
        else if(heap_left.size() < heap_right.size())
        {
            heap_left.push(heap_right.top());
            heap_right.pop();
        }
    }
};

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        LabelOppositeHeap label_opposite_heap;
        for(int i = 0; i < k; ++i)
        {
            label_opposite_heap.insert(nums[i]);
        }
        int n = nums.size();
        vector<double> result(n - k + 1);
        for(int i = k; i < n; ++i)
        {
            result[i - k] = label_opposite_heap.query();
            label_opposite_heap.index_delete(nums[i - k]);
            label_opposite_heap.insert(nums[i]);
        }
        result[n - k] = label_opposite_heap.query();
        return result;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构