下标索引堆：key 是大对象时，如何实现可对给定 key 删改的堆

字数统计: 2.6k字 | 阅读时长: 11分

2020-11-07

摘要: 下标索引堆，思想，代码模板，例子

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$0 背景

(1) 支持按 key 删除的堆

一般的堆不支持按key操作，例如按 key 删除，按 key 修改。

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

如果真有需求的话，可以直接在内部加索引，使得给堆提供 key 之后，对内部可以找到该 key 对应的节点(数组下标)，这种内部加索引的堆为索引堆。

(2) 哈希索引堆

一种直观的想法是直接对 key 做哈希索引，这是首先想到的思路，性能不一定好，但是很直接。参考哈希索引堆。

(3) 标记删除 + 惰性更新

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

(4) 哈希索引堆的索引优化

实战中 key 和索引的结构可以根据场景优化，有些时候甚至可以直接用数组下标代替，省去哈希这一步(性能提升较大)。参考哈希索引堆的索引优化。

$1 下标索引堆

(1) ID从1自增时用vector代替unordered_map的哈希索引堆

为了按 key 删除或修改，采用最直观的对 key 直接加哈希索引形成哈希索引堆。对哈希索引的常规优化，涉及到两个方面：

第一个是在将数据压堆之前分配一个唯一 ID。
第二个是如果分配的 ID 是从 1 开始自增的，将索引堆内部的 unordered_map 改为 vector。

在哈希索引堆的基础上增加以上两个优化，形成了 ID从1自增时用vector代替unordered_map的哈希索引堆，并解决滑动窗口最大值问题，性能取得明显优化。

参考哈希索引堆的索引优化

遗留问题：ID 越来越大

ID从1自增时用 vector 代替 unordered_map 的哈希索引堆有个问题，就是数据经过多次插入删除之后，数据数组在交替的插入删除操作下大致保持平衡，而分配的 ID 却在这个过程中越来越大。

此时按照是否了解数据量，有两种方法。

<1> 数据量未知

在外面维护一个已删除 ID 的有序集合，数据插入前分配 ID 时，优先分配已经删除的 ID，这样索引数据长度也会在交替的插入删除下大致保持平衡。

将已删除 ID 从小到大重新分配，本身是一个比较独立的组件，经常与各种加索引的数据【设计难题】力扣1500-设计文件分享系统。

这种办法可以适应数据量不确定的场景，调用方需要额外的成本维护数据和分配的 ID 的对应关系，以及哪些 ID 是被删掉的。

实践起来未必比索引堆内部用 unordered_map 但是调用方不用额外维护 ID 信息的做法好。因为内部虽然把 unordered_map 改成了 vector，但是外面需要数据结构维护 ID 信息。

<2> 了解总数据量

建堆的时候直接开长为 N 的数据数组和索引的空间，此后都在这个空间下操作，不会触发扩容。

这种方法相当于对 ID 无限增长的问题视而不见，但是因为能保证数据量小于 N，视为没有这个问题。

这种办法的场景限制比较大(提前知道数据量 <= N)，但是分配的 ID 具有下标意义，因此调用方不需要额外成本就可以把数据和 ID 对应起来。

当外面是通过遍历一个固定长度的数组来遍历所有数据的时候，这种办法很适用，数组下标直接就是 ID，并且大小可控。

(2) 内部树形索引

当已知数据量 <= N 的情况下用这种 ID 从 1 自增时用 vector 代替 unordered_map 的哈希索引堆是一种比较有效的索引堆。

如果数据数组中的对象很重的时候，维护堆的元素大量交换产生的代价不可接受的话，可以让存数据的数组 data 不变，中间加一层数组形式的树形索引 indexes。

data 只有在插入的时候改变。
删除的时候, data 不做改变，只在 indexes 做相应的调度和修改。
调整堆的过程在 indexes 做。

堆中维护的数据在调用方经常是通过线性遍历的方式访问的，有可能是接收数据流，有可能是直接遍历数组或其它数据结构。这样数据按照访问次序可以给定一个 ID，如果是从前向后遍历数组，那么可以直接把数组下标作为 ID。

由于有数据 <= N 这个可控的条件，因此调用方很容易维护数据和 ID 的对应关系。

data 除了插入的时候是不修改的，即插入的时候插入到 data 的哪个下标 idx，直到该数据删除的时候依然在 data[idx]，该数据的索引也是 idx。

每个数据在堆中维护的整个生命周期，data 对调用方都是透明的。因此数据在 data 的什么位置完全由调用方指定，插入的时候就需要提供下标，即该数据插入在 data 的什么位置。

而数据的索引恰恰是数据插入时在 data 上的下标，即 push(int val, int idx) 插入时提供的 idx 交给索引堆的既是该数据的索引，也是数据 val 在 data 上的下标。

(3) 外层哈希索引

充当哈希索引的 idx，通过 mapping 指向该数据在索引堆的逻辑位置，即 mapping[idx] 指向的是 indexes 中对应的位置。data[indexes[i]] 是按照堆的特性排序的。

数据的索引并不需要在 data 的节点上保存了，因为 data[idx] 的索引就是 idx，而 idx 本身就是插入时由调用方提供的并且整个生命周期不变，因此插入的时候不需要再把索引包装成结构体存在 data 上了。

(4) 堆的调整

调整的时候，通过比较 data[indexes[i]] 和 data[indexes[j]] 决定是否要交换，如果交换，则交换 indexes[i] 和 indexes[j]。

$2 下标索引堆的实现

数据结构设计

vector<int> data;
vector<int> indexes; // 数组形式树形索引 i -> data[indexes[i]]
vector<int> mapping; // 数组形式哈希索引 mapping[indexes[i]] = i
                     // data[i] = data[indexes[mapping[i]]]
int _size;

代码 (C++，模板)

大顶堆，小顶堆只需要把调整对的 push_up 和 push_down 改一下。

class IndexMaxHeap
{
public:
    IndexMaxHeap()
    {
        _size = 0;
    }

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

    int top()
    {
        if(empty())
            return -1;
        return data[indexes[1]];
    }

    int pop()
    {
        if(empty())
            return -1;
        int ans = data[indexes[1]];
        _remove(1);
        return ans;
    }

    void push(int idx, const int key)
    {
        ++idx;
        // 覆盖 data[idx] 的数据, idx 同时也是 key 的索引
        // mapping[idx] := key 在堆中的逻辑位置，即 indexes 中的位置
        if(idx >= (int)data.size())
            dilatation();
        ++_size;
        data[idx] = key;
        mapping[idx] = _size;
        indexes[_size] = idx;
        push_up(_size);
    }

    void remove(int idx)
    {
        ++idx;
        if(mapping[idx] < 0)
            return;
        int i = mapping[idx];
        _remove(i);
    }

    void change(int idx, const int new_key)
    {
        ++idx;
        if(mapping[idx] < 0)
            return;
        if(data[idx] == new_key)
            return;
        data[idx] = new_key;
        int i = mapping[idx];
        push_up(i);
        push_down(i);
    }

    int size()
    {
        return _size;
    }

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

private:
    vector<int> data; // keys
    vector<int> indexes;
    int _size;
    vector<int> mapping; // id -> idxs

    void dilatation()
    {
        int new_capacity = (int)data.size() * 2 + 1;
        vector<int> tmp_data(new_capacity, -1);
        vector<int> tmp_indexes(new_capacity, -1);
        vector<int> tmp_mapping(new_capacity, -1);
        for(int i = 0; i < (int)data.size(); ++i)
        {
            tmp_data[i] = data[i];
            tmp_indexes[i] = indexes[i];
            tmp_mapping[i] = mapping[i];
        }
        data.swap(tmp_data);
        indexes.swap(tmp_indexes);
        mapping.swap(tmp_mapping);
    }

    void _remove(int i)
    {
        if(i > _size)
            return;
        if(i == _size)
        {
            mapping[indexes[_size]] = -2;
            --_size;
            return;
        }
        int idx_i = indexes[i];
        int idx_j = indexes[_size];
        swap(mapping[idx_i], mapping[idx_j]);
        indexes[i] = indexes[_size--];
        mapping[idx_i] = -2;
        push_up(i);
        push_down(i);
    }

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

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

$3 代码测试

239. 滑动窗口最大值

1
2
3

更新窗口端点时:
用 change(id, new_key);             572ms
用 remove(id) + push(new_item);     648ms

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        if(n <= k)
        {
            int mx = nums[0];
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return vector<int>();
        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
        IndexMaxHeap 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.change(i % k, nums[i]);
            // heap.remove(i - k);
            // heap.push(i, nums[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};
            for(int i = 1; i < n; ++i)
                mx = max(mx, nums[i]);
            return vector<int>({mx});
        }
        // 滑动 n - k 次
        // 0..k-1
        IndexMaxHeap 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.change(i % k, nums[i]);
            // heap.remove(i - k);
            // heap.push(i, nums[i]);
            result.push_back(heap.top());
        }
        return result;
    }
};

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

算法数据结构