1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ A normal binary heap will do the job. More involved DSs: Binomial heap, and Fibonacci heap. $\endgroup$ – A.Schulz Jun 12 '13 at 16:23
  • $\begingroup$ @A.Schulz, the regular binary heap is what is causing me headaches at this moment, since its size is static. I'm not completely familiar with these other heaps, but I'll look them up. $\endgroup$ – araruna Jun 13 '13 at 2:10
  • $\begingroup$ You are probably thinking of the Rope data structure... $\endgroup$ – Aryabhata Jun 13 '13 at 5:46
  • 2
    $\begingroup$ @araruna: You dont need to implement a binary heap as an array. You can use a tree-structure linked with pointers instead. $\endgroup$ – A.Schulz Jun 13 '13 at 6:35
  • $\begingroup$ @A.Schulz: indeed, but then this would increase the complexity of the extract-min operations, as we wouldn't know a "maximal" element in constant time to replace the minimum and perform the decrease-key to restore the heap property. insert operations would also be affected, because we woudn't know where to insert the new element preserving the bounded tree height of $O(\log n)$. $\endgroup$ – araruna Jun 13 '13 at 13:37
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The problem is not the amortized time, but the actual CPU time needed to perform the operation. Sometimes I get a heap with more than 200MBs worth of elements or even more. $\endgroup$ – araruna Jun 13 '13 at 2:08
  • $\begingroup$ Please see the edit of the question that states the practical application of this structure, so you can understand how important the CPU time spent is. $\endgroup$ – araruna Jun 13 '13 at 2:18
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Intuitively, Binomial Heaps seem to be better suited for B&B purposes, given that the number of deletions is expected to be greater than the number of insertions, but I'll make a benchmark test before deciding. $\endgroup$ – araruna Jun 13 '13 at 14:16
  • $\begingroup$ How can number of deletions be greater than number of insertions? :-) $\endgroup$ – Aryabhata Jun 14 '13 at 1:24
  • $\begingroup$ Oh, I'm sorry. It's the other way around... =) The worst case would be when the B&B tree empties, then the number of deletions would be equal to the number of insertions. $\endgroup$ – araruna Jun 14 '13 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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