Priority queue for partially ordered priorities with infima

I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than arbitrarily completing the order, I would prefer if the queue was stable in a sense that if there is more than one minimal element, it should return the oldest first.

Is there any heap data structure that would work with partial ordering? Or a modification of regular priority queue to work with it? Common choice for the algorithm I need is simple binary or 4-ary heap, but that does not work with partial ordering.

The priority values support:

• Partial ordering using operation $\preccurlyeq$. It's partial ordering, so it's possible that $a \preccurlyeq b$ is false and $b \preccurlyeq a$ is also false. I write $a \not\lesseqgtr b$ in that case.

• Finding infima (glb) and suprema (lub). $\inf(x_i)$ is the maximal $y$ such that $y \preccurlyeq x_i$. Calculating the infimum of $n$ values takes $O(n)$ time. Infimum (and supremum) of every set exists.

• A linear extension for the partial ordering could be defined. Using it for the priority queue is the easy way out as the algorithm does work that way. But the order affects performance and the order of insertion looks like it should be best in avoiding worst cases.

Additionally the algorithm that I want to use this in needs to know infimum of all priorities in the queue.

The priorities have some real-world meaning, but are subject to change, so it does not seem viable to rely on other properties they could have.

Note: Binary heaps don't work with partial ordering. Assume a binary heap with $a$, $b$ and $c$, where $a \preccurlyeq c$ and $a \not\lesseqgtr b$ and $a \not\lesseqgtr c$. They are positioned in that order, so

a (0)
   /   \
 b (1)   c (2)

now d is inserted. Next free position is 3, the left child of $b$, so we get

a (0)
      /   \
    b (1)   c (2)
  /
d (3)

If $d \preccurlyeq a$ (which impli

Although the exact problem posed in the original question does seem to be difficult (and I would be interested in a solution to that problem, especially the infima finding part). I just wanted to note that if the partially ordered set indeed consists of vectors using a product order, and if it is sufficient to just have the guarantee that the priority queue returns the values in an order that is "compatible" with the partial order (that is, smaller elements are always returned before larger elements), then there is a fairly easy way to do it.

The idea is essentially to find a topological ordering of the partially ordered set. That is, a total order '$\le_T$' such that $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$. For vectors using a product order, this is fairly easy: just use a lexicographical order '$\le_S$', where the first "component" is the sum of all the components used for the product order (the rest of the components are essentially arbitrary, so you could also stick to a weak order). We can then see that
$$\mathbf{a}<\mathbf{b}\implies \forall_i(a_i\le b_i)\text{ and }\exists_i(a_i<b_i)\implies(\sum_i a_i)<(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b}$$
and
$$\mathbf{a}=\mathbf{b}\implies \forall_i(a_i=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$$
and thus that $\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$. We can thus use this order with a priority queue and be sure that smaller elements (in the product order) will always be extracted before larger elements.

StackExchange Computer Science Q#7890, answer score: 3