Java 如何移除 Meldable Heap 中的节点

Question

如何从 Meldable 堆中删除特定节点？我知道如何删除根，然后合并左右节点。我不知道如何找到一个特定的节点，删除它并修复剩余的节点。任何意见，将不胜感激。谢谢

Answer 1

当你移除堆中间的一个节点时，你做的第一件事就是更新父节点，这样父节点就不再指向被移除的节点。本质上，您现在有两个堆：原始堆和以要删除的节点为根的子堆。

然后，在第二个堆（以要删除的节点为根的堆）中调用remove。这将删除最小的项目，即您要删除的节点，并修复堆。

最后，您将第二个堆与主堆合并。

困难的部分是找到要删除的节点。这需要遍历树结构，检查每个节点的键。

如果要避免顺序扫描，则必须创建一个单独的数据结构，例如将键映射到堆节点的哈希映射。通常你会有一个包装数据结构。像下面这样的东西，尽管请原谅语法。 Java 不是我的强项:

class IndexableHeap
{
    MeldableHeap theHeap;
    HashMap<key, Node> index

    void add(node)
    {
        theHeap.add(node);
        index.add(node.x, node);
    }

    remove()
    {
        theHeap.remove(node);
        index.remove(node.x);
    }
}

我想你明白了。

Java 如何移除 Meldable Heap 中的节点

Java How to remove Node in Meldable Heap

java

heap