< prev | up | next >

PDF logo A rearrangement step with potential uses in priority queues

by Boris Alexeev and M. Brian Jacokes

Abstract

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

Approximate citation

Boris Alexeev and M. Brian Jacokes
A rearrangement step with potential uses in priority queues
Note, March 2012.

Useful links

PDF logoDirect PDF link
arXiv icon arXiv online preprint server version
BiBTeX icon Individual BiBTex entry
< prev | up | next >