Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from programmers.stackexchange.com Jan 11 '13 at 22:56

This question came from our site for professional programmers interested in conceptual questions about software development.

    
Have you considered an Indexed Priority Queue? –  hulkmeister Jan 9 '13 at 13:25
    
@hulkmeister: Could you please explain how having the queue indexed makes it work with partial ordering (no, plain binary heap does not work with partial ordering)? –  Jan Hudec Jan 9 '13 at 13:46
1  
My thought was that when two items are incomparable, you can use the index to track the order of insert. So compose the priority with the index, and you have unique keys that are comparable even when the priority is not. If this sounds like what you want, I can put it into a complete answer. –  hulkmeister Jan 9 '13 at 14:42
1  
@hulkmeister: Well, the problem is much deeper than that. When a new item is inserted, the priority queue normally compares it with some element. But if they are incomparable, it simply does not know where to insert it. And disambiguation with the index won't work, because the index changes and because it probably wouldn't give total ordering consistent with the priority anyway. –  Jan Hudec Jan 9 '13 at 14:49
    
Can you give some example of this compound type, and when it is incomparable? Is it possible to consider these 'incomparable' values equal? If so, you could store them in the same node in order of insertion. –  Max Jan 9 '13 at 16:18
show 1 more comment

6 Answers 6

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.

share|improve this answer
    
There are many more options. Using one of the components, minimum, maximum, any linear combination with non-negative coefficients at least. Choice of the extension affects how fast the overlaying algorithm will be. –  Jan Hudec Nov 7 '13 at 12:17
add comment

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.

share|improve this answer
3  
That would be great if it could be made a linear extension of the partial ordering. But it isn't. Let's have 3 distinct values, inserted in order a, b, c, such that c ≤ a and b is incomparable with either. The extension with timestamp fills in a ≤' b and b ≤' c, so from transitivity now a should be less than c, but that contradicts the actual ordering. –  Jan Hudec Jan 11 '13 at 7:42
    
Perhaps you confused it with weak ordering. In weak ordering the incomparable elements form equivalence classes, so you can add arbitrary additional criteria. For partial ordering you can't. –  Jan Hudec Jan 11 '13 at 7:59
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Unfortunately I don't see way to efficiently find the list of comparable objects. –  Jan Hudec Jan 11 '13 at 9:41
    
Partially ordered set can indeed be viewed as directed acyclic graph. But one given by adjacency table (function, actually) rather than adjacency list. Finding minima of poset given by adjacency list is easy, but for adjacency table it's a problem. –  Jan Hudec Jan 11 '13 at 10:09
    
Minima are well-defined in the original set as well. I don't see how finding the connected components could help, since they are not complete graphs. –  Jan Hudec Jan 11 '13 at 10:10
1  
You seem to assume that the Hasse diagram is a forest of unary trees (equivalently path graphs), but the question already states that it's a product order, so a multi-dimensional lattice. –  Peter Taylor Jan 11 '13 at 18:41
add comment

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)
share|improve this answer
add comment

Usual heap behaviour is to append the new value to the back, and then sift up while it compares greater than its parent.

If you write a comparison which returns the same for the parent and child are not comparable case as for parent is greater than child, sift up should still terminate at the right point.

Does that count as a sufficiently stable ordering for your purposes?


To clarify, take the example from your comment: a > b, and c is not comparable to a or b:

  • a then b then c => a, b, c ... this is in heap order already, and nothing ever moves in sift-up
  • b, a, c => a, b, c ... a is sifted up to its correct place, and again we're in correct heap order
  • a, c, b => a, c, b ... b can't sift up because it is not comparable with c, but this leaves them in FIFO order as you asked
  • c, b, a => c, a, b ... a and b are in the correct relative order, but neither can get ahead of c because they can't be compared with it

so, the result depends on the order of insertion - this seems to match what you ask for, but I'm not sure whether it's really what you want. If it isn't, could you show the result you hoped to see?


OK, so from your comment (and the edit to your question), you do want "comparable" elements to leapfrog "non-comparable" ones and find the correct place under the ordering, if there is one. I asked about this because I wasn't sure how to interpret

if some elements are incomparable, it returns them in the order they were inserted

(d and b are pairwise incomparable in your edit, but you don't want them in the order they were inserted).

My next question would have been about the relationship between the "comparable" and "non-comparable" elements, but I see you've revealed now that they're vectors in product order (it wasn't clear whether some elements were pairwise-incomparable with everything, like NaN, or what).

So, if I take your new example and assign vector values, is it correct that this is an example where b is not comparable to anything else:

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

and it should sort to this:

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

?

share|improve this answer
    
I explicitly mentioned in the question that it won't work, because I thought I have a counter-example, but I am not so sure with it now. Can you prove that such queue would be sound (for deletemin, insert and update too)? And remember, that it's possible that a ≤ b, but c is not comparable (and would therefore compare "equal" with the above rule) to either of them. –  Jan Hudec Jan 9 '13 at 19:23
    
Well, that's not proof yet. Don't care for the order yet and proof that such heap always has minimal element at the top (note: (more) common convention and the actual need of the algorithm is minimal at the top, so if a > b, b comes first). –  Jan Hudec Jan 9 '13 at 20:04
    
Actually I suspect there is counter-example. Suppose a, b and c are in the heap, a ≤ b and a ≤ c, a is top, b is left child, c is right child. Now d comes that d ≤ c and incomparable with a and b. It is inserted as child of b, is not less and stays there. Now comes e that is c ≤ e (thus also a ≤ e) and incomparable to b. So e goes in as right child of b and stays. Now extract a (OK, a is minimal), e gets swapped in it's place and sifted down. It is incomparable to b, but less than c, so swaps with c. Now extract c, WRONG, d ≤ c. –  Jan Hudec Jan 9 '13 at 20:17
    
If you find a mistake in the previous comment (which would need to have a form of inequality that has to hold because of transitivity and I missed it), you'd still have a chance. Otherwise it won't work. –  Jan Hudec Jan 9 '13 at 20:19
1  
Ok, even simpler counter-example. Suppose a, b and c are in the heap, a ≤ c, b is incomparable with either. a is top, b is left child, c is right child. d comes in so that d ≤ a (thus d ≤ c) and incomparable with b. Next free slot is as left child of b and d is incomparable, so it stays there. Now extract a, WRONG, d ≤ a. Note that whether a ≤ c or not does not matter, the situation is the same if they were incomparable. –  Jan Hudec Jan 9 '13 at 20:27
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.