language-agnostic - 可搜索的堆结构

Question

问题是通过两种不同的方法访问一系列值。首先，按优先级；用堆就可以很简单地实现这一点。此外，必须能够使用一个或多个符号“标记”每个值，通过这些符号可以访问项目列表。

通过在两个不同的结构中引用相同的数据，这很容易有效地实现。然而，这些必须形成一个有凝聚力的队列。因此，通过一个结构删除的项目也必须从另一个结构中删除，而堆不太适合这种操作。

是否有一种数据结构能够通过一个值提供有效的排序(非常适合推送/弹出)，而不会完全降低在任意位置查找/删除节点的性能？

Answer 1

如果您知道要删除哪个元素，则可以在 O(log(n)) 时间内从二叉堆中删除任何元素。任何节点都可以被视为有效的“子堆”，您可以像对整个节点一样使用delete-max(或delete-min)操作。

唯一的问题是你如何知道要删除哪一个？我想我有一个解决方案。对具有对其堆节点的引用的存储类使用包装器，并从包装器析构函数中删除该节点。当您想从集合中删除任何元素时，您只需通过任何索引删除包装器即可，它会处理其余的事情。当您向集合中插入某些内容时，您需要创建一个包装对象并传递对其堆节点的引用。

这里是一些 C++ 代码:

template <class T> class Wrapper {
    T data;
    HeapNode* index_heap;
    Foo* index_tags;
    Bar* index_queue;

    public: ~Wrapper() {
        index_heap->delete_max();
        index_tags->delete_foo();
        index_queue->delete_bar();
    }
};