Java 如何删除Meldable Heap中的节点

Question

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

Answer 1

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

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

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

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

如果要避免顺序扫描，则必须创建单独的数据结构，例如将键映射到堆节点的 HashMap 。通常您会有一个包装数据结构。类似于下面的内容，尽管请原谅语法。 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);
    }
}

我想你明白了。