Double-ended priority queue using dual structure approach

Question

I'm trying to understand how to build a double-ended priority queue using two heaps: a min heap and a max heap. My thinking so far is that I'll need one array to store the min heap, and another to store the max heap, and then I need to figure out how to connect the relevant entries in the two arrays to each other. E.g., I need to make sure that wherever the value "12" ends up in the min heap somehow points to where the value "12" is in the max heap, and vice versa. I understand that in theory, but I have no idea how to go about actually implementing it.

How can I make elements in one array point to elements in another array in an efficient and flexible way? Especially since each array is going to be continually re-shuffled throughout the program.

Not sure if that made sense, but any help is most appreciated. Thanks.

Thanks for the replies. Not sure I get it, but I'll jump back in based on the responses. — A B

c.s. c.s. · Accepted Answer · 2013-07-26T06:50:59

How can I make elements in one array point to elements in another array in an efficient and flexible way?

Use a pointer to each element that knows what object is its counter-part e.g.

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);

If your requirements are that each object knows its position (i.e. index) in each list this might require a bit of more work depending on how you implement the heaps. You should make sure that they set the location of each element, every time they change its position. So the Element object would become location aware.

Double-ended priority queue using dual structure approach

2 Answers