Priority queue with ubounded number of elements (i.e., with dynamic storage)

Question

I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for its number of elements (like a tree structure, that is bounded only by the computer's available memory, and unlike a traditional heap, that uses an static array, which is too costly to augment).

The reason is that I'm implementing a program that makes use of a priority queue and I don't know a priori how many elements I'm going to insert in this queue at once, so sometimes I'm out of space to add another element.

There is no way to estimate this number, and to create a huge array to support a static type of queue is a terrible option, as maybe not even a half of it will be used and I'll be short on memory to allocate other objects.

I've heard of something like a Dynamic Heap (or something in the like) that is some sort of linked list of arrays, whose elements are dynamically allocated when needed, but I'm not sure this is the best strategy to follow, moreover, I would like to know if there were other options.

---

Just for the record, I'm implementing a Branch-and-Bound algorithm for solving a linear integer optimization problem, with each node stored on the queue being the abstraction of an active node on the algorithm. The number of active nodes cannot be estimated at any time, so a theoretically unbounded queue would help a lot.

Answer 1

I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it to two-thirds of its size.

Answer 2

At the cost of some space and time (affecting only the constant factors), you can implement vectors (i.e. dynamic arrays) whose operations are $O(1)$ worst case (and not amortized).

If you have $n$ elements in the vector and it is full, you allocate a new chunk to hold $\alpha n$ elements (where $\alpha \gt 1$ is some constant, which you can parametrize). Don't copy over the old elements just yet (like the standard vector algorithm), and keep the old array around. Instead of using $\alpha n$ space, you use $(1+\alpha)n$ space.

Every time a new element is inserted (i.e. index beyond $n$), you insert that into the new array, and you copy over a constant number of elements (determined based on $\alpha$ and your machine/insert characteristics) from the old array to the new.

You deallocate the old array only when you have made sufficient insertions to copy over all the old elements.

Array reads will also become slightly slower, as you will now have a switch to determine which array to access (but still $O(1)$), and memory usage will be slightly more, but that can be tweaked by choosing appropriate $\alpha$.

Answer 3

After browsing for "priority queue" pages, I was finally convinced that some of the already known dynamic storage data structures can be adapted trivially to provide a good priority queue.

I'd already heard of the Binomial Heaps and Fibonacci Heaps, but I didn't know their implementation specifics. Self-balancing binary search trees, like AVL Trees and Red-Black Trees can also be used, since keeping track of the smallest element is simple and updating this reference is fairly cheap.

Then I discovered a new data structures: Brodal Queues, which seems to be very hard to be used in practise, according to the author.

Bear in mind that none of these structures rely on static arrays, but in linked structures, so that rearranging them does not involve lots of memory moves. This is the property I was looking for.

I'm sure that there are more structures like these that can be used as theoretically unbounded priority queues, and this is why I'm marking this answer as a community wiki, so others can increase this list.