Is there a stable heap? Is there a priority queue data structure that supports the following operations?


Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum priority, breaking ties by insertion order.


Thus, after Insert(a, 1), Insert(b, 2), Insert(c, 1), Insert(d,2), a sequence of StableExtractMin's would return a, then c, then b, then d.

Obviously one could use any priority queue data structure by storing the pair $(p, time)$ as the actual priority, but I'm interested in data structures that do not explicitly store the insertion times (or insertion order), by analogy to stable sorting.

Equivalently(?): Is there a stable version of heapsort that does not require $\Omega(n)$ extra space?
The Bently-Saxe method gives a fairly natural stable priority queue.

Store your data in a sequence of sorted arrays $A_0,\ldots,A_k$.  $A_i$ has size $2^i$.  Each array also maintains a counter $c_i$. The array entries $A_i[c_i],\ldots,A_i[2^i-1]$ contain data.

For each $i$, all elements in $A_i$ were added more recently than those in $A_{i+1}$ and within each $A_i$ elements are ordered by value with ties being broken by placing older elements ahead of newer elements.  Note that this means we can merge $A_i$ and $A_{i+1}$ and preserve this ordering.  (In the case of ties during the merge, take the element from $A_{i+1}$.) 

To insert a value $x$, find the smallest $i$ such that $A_i$ contains 0 elements, merge $A_0,\ldots,A_{i-1}$ and $x$, store this in $A_i$ and set $c_0,\ldots,c_i$ appropriately.

To extract the min, find the largest index $i$ such that the first element in $A_i[c_i]$ is minimum over all $i$ and increment $c_i$.

By the standard argument, this gives $O(\log n)$ amortized time per operation and is stable because of the ordering described above.

For a sequence of $n$ insertions and extractions, this uses $n$ array entries (don't keep empty arrays) plus $O(\log n)$ words of bookkeeping data.  It doesn't answer Mihai's version of the question, but it shows that the stable constraint doesn't require a lot of space overhead.  In particular, it shows that there is no $\Omega(n)$ lower-bound on the extra space needed.

Update: Rolf Fagerberg points out that if we can store null (non-data) values, then this whole data structure can be packed into an array of size $n$, where $n$ is the number of insertions so far.

First, notice that we can pack the $A_k,\ldots,A_0$ into an array in that order (with $A_k$ first, followed by $A_{k-1}$ if it's non-empty, and so on).  The structure of this is completely encoded by the binary representation of $n$, the number of elements inserted so far.  If the binary representation of $n$ has a 1 at position $i$, then $A_i$ will occupy $2^i$ array location, otherwise it will occupy no array locations.

When inserting, $n$, and the length of our array, increase by 1, and we can merge $A_0,\ldots,A_i$ plus the new element using existing in-place stable merging algorithms.

Now, where we use null values is in getting rid of the counters $c_i$.  In $A_i$, we store the first value, followed by $c_i$ null values, followed by the remaining $2^i-c_i-1$ values.  During an extract-min, we can still find the value to extract in $O(\log n)$ time by examining $A_0[0],\ldots,A_k[0]$.  When we find this value in $A_i[0]$ we set $A_i[0]$ to null and then do binary search on $A_i$ to find the first non-null value $A_i[c_i]$ and swap $A_i[0]$ and $A_i[c_i]$.

The end result: The entire structure can be implemented with one array whose length is increment with each insertion and one counter, $n$, that counts the number of insertions.