A simplification of a run-relaxed heap, called a *relaxed weak
queue*, is presented. This new priority-queue implementation
supports all operations as efficiently as the original: *find*-*min*,
*insert*, and *decrease* (also called *decrease*-*key*) in *O*(1)
worst-case time, and *delete* in *O*(lg *n*) worst-case time, *n*
denoting the number of elements stored prior to the operation. These
time bounds are valid on a pointer machine as well as on a
random-access machine. A relaxed weak queue is a collection of at
most ⌊ lg *n* ⌋ + 1 perfect weak heaps, where there are in
total at most ⌊ lg *n* ⌋ + 1 nodes that may violate
weak-heap order. In a pointer-based representation of a perfect
weak heap, which is a binary tree, it is enough to use two pointers
per node to record parent-child relationships. Due to *decrease*,
each node must store one additional pointer. The auxiliary data
structures maintained to keep track of perfect weak heaps and
potential violation nodes only require *O*(lg *n*) words of
storage. That is, excluding the space used by the elements
themselves, the total space usage of a relaxed weak queue can be as
low as 3 *n* + *O*(lg *n*) words. |