Is there a stable heap?

Question

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?

Answer 1

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.

Answer 2

I'm not sure what your constraints are; does the following qualify? Store the data in an array, which we interpret as an implicit binary tree (like a binary heap), but with the data items at the bottom level of the tree rather than at its internal nodes. Each internal node of the tree stores the smaller of the values copied from its two children; in case of ties, copy the left child.

To find the minimum, look at the root of the tree.

To delete an element, mark it as deleted (lazy deletion) and propagate up the tree (each node on the path to the root that held a copy of the deleted element should be replaced with a copy of its other child). Maintain a count of deleted elements and if it ever gets to be too large a fraction of all elements then rebuild the structure preserving the order of the elements at the bottom level — the rebuild takes linear time so this part adds only constant amortized time to the operation complexity.

To insert an element, add it to the next free position on the bottom row of the tree and update the path to the root. Or, if the bottom row becomes full, double the size of the tree (again with an amortization argument; note that this part is not any different from the need to rebuild when a standard binary heap outgrows its array).

It's not an answer to Mihai's stricter version of the question, though, because it uses twice as much memory as a true implicit data structure should, even if we ignore the space cost of handling deletions lazily.

Answer 3

Is the following a valid interpretation of your problem:

You have to store N keys in an array of A[1..N] with no auxiliary information such that you can support: * insert key * delete min, which picks the earliest inserted element if there are multiple minima

This appear quite hard, given that most implicit data structures play the trick of encoding bits in the local ordering of some elements. Here if multiple guys are equal, their ordering must be preserved, so no such tricks are possible.

Interesting.

Answer 4

Short answer : You can't.

Slightly longer answer :

You'll need $\Omega(n)$ extra space to store the "age" of your entry which will allow you to discriminate between identical priorities. And you'll need $\Omega(n)$ space for information that will allow fast insertions and retrievals. Plus your payload (value and priority).

And, for each payload you store, you'll be able to "hide" some information in the address (e.g. $addr(X) < addr(Y)$ means Y is older than X). But in that "hidden" information, you'll either hide the "age", OR the "fast retrieval" information. Not both.

---

Very long answer with inexact flaky pseudo-math :

Note : the very end of the second part is sketchy, as mentioned. If some math guy could provide a better version, I'd be grateful.

Let's think about the amount of data that is involved on an X-bit machine (say 32 or 64-bit), with records (value and priority) $P$ machine words wide.

You have a set of potential records that is partially ordered : $(a,1) < (a,2)$ and $(a,1) = (a,1)$ but you can't compare $(a,1)$ and $(b,1)$.

However you want to be able to compare two non-comparable values from your set of records, based on when they were inserted. So you have here another set of values : those that have been inserted, and you want to enhance it with a partial order : $X < Y$ iff $X$ was inserted before $Y$.

In the worst-case scenario, your memory will be filled with records of the form $(?,1)$ (with $?$ different for each one), so you'll have to rely entirely upon the insertion time in order to decide which one goes out first.

• The insertion time (relative to other records still in the structure) requires $X - log_2(P)$ bits of information (with P-byte payload and $2^X$ accessible bytes of memory).
• The payload (your record's value and priority) requires $P$ machine words of information.

That means that you must somehow store $X - log_2(P)$ extra bits of information for each record you store. And that's $O(n)$ for $n$ records.

Now, how much bits of information does each memory "cell" provide us ?

• $W$ bits of data ($W$ being the machine word width).
• $X$ bits of address.

Now, let's assume $P \geq 1$ (payload is at least one machine word wide (usually one octet)). This means that $X - log_2(P) < X$, so we can fit the insertion order information in the cell's address. That's what happening in a stack : cells with the lowest address entered the stack first (and will get out last).

So, to store all our information, we have two possibilities :

• Store the insertion order in the address, and the payload in memory.
• Store both in memory and leave the address free for some other usage.

Obviously, in order to avoid waste, we'll use the first solution.

---

Now for the operations. I suppose you wish to have :

• $Insert(task, priority)$ with $O(log n)$ time complexity.
• $StableExtractMin()$ with $O(log n)$ time complexity.

Let's look at $StableExtractMin()$ :

The really really general algorithm goes like this :

1. Find the record with minimum priority and minimum "insertion time" in $O(log n)$.
2. Remove it from the structure in $O(log n)$.
3. Return it.

For example, in the case of a heap, it will be slightly differently organized, but the work is the same : 1. Find the min record in $0(1)$ 2. Remove it from the structure in $O(1)$ 3. Fix everything so that next time #1 and #2 are still $O(1)$ i.e. "repair the heap". This needs to be done in "O(log n)" 4. Return the element.

Going back to the general algorithm, we see that to find the record in $O(log n)$ time, we need a fast way to choose the right one between $2^(X - log_2(P))$ candidates (worst case, memory is full).

This means that we need to store $X - log_2(P)$ bits of information in order to retrieve that element (each bit bisects the candidate space, so we have $O(log n)$ bisections, meaning $O(log n)$ time complexity).

These bits of information might be stored as the address of the element (in the heap, the min is at a fixed address), or, with pointers for example (in a binary search tree (with pointers), you need to follow $O(log n)$ on average to get to the min).

Now, when deleting that element, we'll need to augment the next min record so it has the right amount of information to allow $O(log n)$ retrieval next time, that is, so it has $X - log_2(P)$ bits of information discriminating it from the other candidates.

That is, if it doesn't have already enough information, you'll need to add some. In a (non-balanced) binary search tree, the information is already there : You'll have to put a NULL pointer somewhere to delete the element, and without any further operation, the BST is searchable in $O(log n)$ time on average.

After this point, it's slightly sketchy, I'm not sure about how to formulate that. But I have the strong feeling that each of the remaining elements in your set will need to have $X - log_2(P)$ bits of information that will help find the next min and augment it with enough information so that it can be found in $O(log n)$ time next time.

The insertion algorithm usually just needs to update part of this information, I don't think it will cost more (memory-wise) to have it perform fast.

---

Now, that means that we'll need to store $X - log_2(P)$ more bits of information for each element. So, for each element, we have :

• The insertion time, $X - log_2(P)$ bits.
• The payload $P$ machine words.
• The "fast search" information, $X - log_2(P)$ bits.

Since we already use the memory contents to store the payload, and the address to store the insertion time, we don't have any room left to store the "fast search" information. So we'll have to allocate some extra space for each element, and so "waste" $\Omega(n)$ extra space.

Answer 5

If you implement your priority queue as a balanced binary tree (a popular choice), then you just have to make sure that when you add an element to the tree, it gets inserted to the left of any elements with equal priority.
This way, the insertion order is encoded in the structure of the tree itself.

Answer 6

I don't think that's possible

concrete case:

       x
    x    x
  x  x  1  x
1  x  

min heap with all x > 1

heapifying will eventually give something a choice like so

       x
    1    1
  x  x  x  x
x  x  

now which 1 to propagate to root?