java - 使用双重结构方法的双端优先级队列

Question

我试图了解如何使用两个堆构建双端优先级队列：最小堆和最大堆。到目前为止，我的想法是我需要一个数组来存储最小堆，另一个来存储最大堆，然后我需要弄清楚如何将两个数组中的相关条目相互连接。例如，我需要确保值“12”最终在最小堆中以某种方式指向值“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 检索它）。我不明白互相引用的目的是什么。如果要添加和删除，则必须为此编写逻辑。