A rearrangement step with potential uses in priority queues
A rearrangement step with potential uses in priority queuesLink-based data structures, such as linked lists and binary search trees, have many well-known rearrangement steps allowing for efficient implementations of insertion, deletion, and other operations. We describe a rearrangement primitive designed for link-based, heap-ordered priority queues in the comparison model, such as those similar to Fibonacci heaps or binomial heaps.
In its most basic form, the primitive rearranges a collection of heap-ordered perfect binary trees. Doing so offers a data structure control on the number of trees involved in such a collection, in particular keeping this number logarithmic in the number of elements. The rearrangement step is free from an amortized complexity standpoint (using an appropriate potential function).
Boris Alexeev and M. Brian Jacokes
A rearrangement step with potential uses in priority queues
Note, March 2012.
| | Direct PDF link |
 | arXiv online preprint server version |