I am envisioning a priority queue that is a bit strange. It represents wanting to do a depth-first left-to-right walk of a tree, but allowing for parallel workers where there can be time between assigning a node to a worker and getting new child nodes back to explore, leaving the depth-first left-to-right property as a best effort.

The priority queue $Q$ is always initialized with a single element $r$. Then we have two operations:

  1. $\texttt{extract-min}(Q)$ finds the least element $x \in Q$, removes it from the data structure and returns it to us, along with an arbitrary handle $h_x$ that represents the removal of $x$.

  2. $\texttt{re-insert}(Q, h_x, a_1, a_2, \dots, a_n)$ inserts prioritized elements $a_1 < a_2 < \dots < a_n$ into the data structure such that for any $l \in Q$ where $l < x$ we have $l < a_1$ and for any $g \in Q$ where $x < g$ we have $a_n < g$. Here $a < b$ means that $a$ is prioritized before $b$ (and will thus be extracted earlier). This consumes handle $h_x$, thus not allowing multiple re-insertions.

Note that the priorities are entirely lexicographically determined by the re-insertions, at no point do we actually compare any objects (the elements of the priority can be arbitrary objects which may not be comparable or have observable properties at all). Essentially our priority queue represents a tree $T$ where after starting with a single unpainted root node $r$:

  1. $\texttt{extract-min}(T)$ finds the first unpainted leaf node $x$ in the pre-order left-to-right traversal and paints it with a unique color $h_x$.

  2. $\texttt{re-insert}(T, h_x,a_1,a_2,\dots,a_n)$ adds new leaves $a_1, a_2, \dots, a_n$ (listed in left-to-right order) as children to the node $x$ painted with color $h_x$. Node $x$ is now painted black so it may never have children added again.

Is it possible to implement both operations in $O(1)$?

Important note: $\texttt{extract-min}$ may be called an arbitrary number of times before a $\texttt{re-insert}$ with an old handle happens. However each handle may only be used once.

  • $\begingroup$ For starters, if we start with only one element, won't this mean that we always have at most one handle to use? Also, in the $re-insert$ operation: if $l<x\implies l<a_1$ and $r>x\implies r>a_n>a_1$, then won't this mean that $a_1=x$ (and thus also $n=1$ always)? $\endgroup$
    – nir shahar
    Apr 1, 2022 at 21:59
  • $\begingroup$ @nirshahar We start with one element, $r$ but then I could, say, re-insert 5 elements after removing $r$, using the handle $h_r$. The priority relation between $a_i$ and $x$ when $a_i$ is re-inserted using handle $h_x$ is irrelevant because they will never be in the priority queue simultaneously. However I've been sloppy and accidentally re-used the symbol $r$ for both the initial element and "elements to the right". Let me fix that. $\endgroup$
    – orlp
    Apr 1, 2022 at 22:24
  • $\begingroup$ Doesn't the same argument still apply? My point is that if $\forall m,M: m<x<M\implies m<a_1<M$, then doesn't that mean that $x=a_1$ (since otherwise, for example, if $a_1>x$, we could choose $ M=\frac{a_1+x}{2}>x $ but $a_1>M$) $\endgroup$
    – nir shahar
    Apr 1, 2022 at 22:34
  • $\begingroup$ @nirshahar It's a partially ordered set. There is no defined order between an element $x$ and the sequence of elements $a_1, a_2, \dots, a_n$ that replaces it. All that section is saying that if something was ordered before $x$, it will still be ordered before the elements that replaced $x$, and vice versa for objects that were ordered after $x$. In particular, the objects in question are not numbers or integers. $\endgroup$
    – orlp
    Apr 1, 2022 at 22:40
  • 1
    $\begingroup$ And finally when I say "for all $l < x$ or all $x < g$" I only mean to make a statement about how objects are prioritized in the queue. The ordering outside of the priority queue is meaningless and non-existent. So yes, $l, g \in Q$. Allow me to clarify that in the question by adding it in. $\endgroup$
    – orlp
    Apr 1, 2022 at 22:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.