A rearrangement step with potential uses in priority queues

Link-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).

No reviews yet.

No comments yet.