Priority queue for partially ordered priorities with infima

Question

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:

1. 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.
2. 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.
3. 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 implies $d \preccurlyeq c$ from transitivity, but does not say anything about $d$ and $b$) and $d \not\lesseqgtr b$, then $d$ does not get swapped with $b$, because it's not less. But it actually is less than $a$, but it's not compared with it, so now the main heap invariant does not hold; top is not minimal.

I suspect a forest of heaps somewhat in style of binomial heap could be made to work. Basically it's important to always compare new values with root and only link together comparable elements. It would make the trees in the forest randomly sized and thus make the complexity dependent on number of mutually incomparable sets in the heap. I somewhat suspect the complexity can't be fixed (we have to keep comparing until we hit a comparable element) I might have missed something, so I am leaving this open.

---

Note: The ordering is partial and while there are ways to define a linear extensions for it, adding a timestamp and using it as secondary criterion is not one of them. Suppose we assigned the timestamp $t(a)$ for each $a$ and defined the ordering $\preccurlyeq'$ as $a \preccurlyeq' b$ iff $a \preccurlyeq b$ or ($b \not\preccurlyeq a$ and $t(a) \le t(b)$. Then suppose we have distinct $a$, $b$, $c$, such that $t(a) \le t(b) \le t(c)$ and $c \le a$. Then $a \preccurlyeq' b$ and $b \preccurlyeq' c$, but $c \preccurlyeq' a$, so the relation is not transitive and therefore is not an ordering at all. This kind of extending only works for weak orderings, but not partial ones.

---

Edit: I realized that not only is infimum of any set defined, but I actually need to be able to get infimum of elements currently in the queue efficiently. So I am now contemplating whether adding special nodes containing infima of subtrees to some common heap structure would help.

Answer 1

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.

Answer 2

What's wrong with making your partial ordering complete?

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.

If you prefer 'oldest first', then your order is effectively complete; 'incomparable' items are comparable by age.

Add a timestamp (or any other monotonously growing integer) to each item and use it if 'real' comparison is impossible.

Answer 3

EDIT: this seems to be an interesting problem, and I had a little research about it. I suggest you read the following:

1. Darell Raymond. Partial order databases, PhD Thesis, University of Waterloo.

I suggest you read this paper: Daskalakis, Constantinos, et al. "Sorting and selection in posets." SIAM Journal on Computing 40.3 (2011): 597-622.

The authors presents here a data structure called ChainMerge that accepts a poset and a chain decomposition of the poset into $q$ chains. The size of the data structure is $O(n q)$. The authors presents an algorithm for finding the minimas that runs in $O(w n)$ where $w$ is an upper bound on the width of the poset. .. I thought maybe this is interesting.

Note: I deleted a previous naive answer. Please click on edit to see it.

Answer 4

My use of terminology may be incorrect. Please edit my answer directly to fix any problems you find.

---

First, mutually incomparable sets need to be detected from the inputs.

For example, there may be 5 objects, a, b, c, d, e, but their partial ordering form two disconnected graphs:

• a ≤ b ≤ c
• d ≤ e
• but any of {a, b, c} is incomparable with any of {d, e}.

These mutually incomparable sets need to be detected first, before the objects can be stored into an appropriate data structure. This can be done with a Union find algorithm

---

For efficiency, the insertion of a new object needs to have an efficient way of finding "the list of existing objects which are comparable with this new object".

---

Now, within each subset (respectively {a, b, c} and {d, e}), the minima should be well-defined. (For each subset there can be one or more minima, due to partial ordering.)

I see this as a directed acyclic graph. Trying to fit it into a heap seems disastrous.

---

To extract the minima from this composite data structure, the next step is to get the list of all minima from all subsets, pick the one with the earliest timestamp, and remove and return this object.

Answer 5

A project I'm working on involves a similar problem (incidentally I'm also using the partial order of vectors). We already had a quadratic time algorithm for sorting a randomly ordered list, and I developed an insertion algorithm by observing its behaviour when only one object was out of order. We don't know whether or not this is the fastest possible implementation.

Here is some pseudocode.

class PartialOrderPriorityQueue
   q <- empty list
   method insert (n):
     for i <- 0 to (q.length - 1):
       if q[i] <= n:
         t <- q[i]
         q[i] <- n
         n <- t
     q.append(n)

   method pop():
     return q.remove(0)