采用双结构方法的双端优先级队列

Question

我试图了解如何使用两个堆构建双结束优先级队列:最小堆和最大堆。到目前为止，我的想法是，我需要一个数组来存储最小堆，另一个数组存储最大堆，然后我需要知道如何将两个数组中的相关条目连接到另一个数组中。例如，我需要确保值"12“在min堆中的任何位置指向值"12”在最大堆中的位置，反之亦然。我在理论上理解这一点，但我不知道如何实际实现它。

如何使一个数组中的元素以高效和灵活的方式指向另一个数组中的元素？特别是因为每个数组都将在整个程序中不断地被重新洗牌。

不确定这是否有意义，但任何帮助都是最感谢的。谢谢。

Answer 1

如何使一个数组中的元素以高效和灵活的方式指向另一个数组中的元素？

使用指向每个元素的指针，这些元素知道其反部分是什么对象。

public class Element<T> {
    T otherElement;   

    public void setOther(T element) {
        this.otherElement = element;
    }
}

// when you create the objects
Element<String> one = new Element();
Element<String> two = new Element();

// now both elements know about each other and they can be to whatever list/array etc they want
one.setOther(two);
two.setOther(one);

如果您的要求是每个对象都知道它在每个列表中的位置(即索引)，这可能需要更多的工作，这取决于您如何实现堆。您应该确保每次更改元素位置时，它们都会设置每个元素的位置。因此，Element对象将成为位置感知。

Answer 2

最终您将创建包装器对象，并将其存储在数组或映射中(如果您希望稍后使用id检索它)。我不明白相互指代的目的是什么。如果您想要添加和删除，您必须为此编写逻辑。