\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for
M. D. Atkinson, S. A. Linton and L. A. Walker, Priority Queues and Multisets
A priority queue, a container data structure equipped with
the operations insert and delete-minimum, can re-order its
input in various ways, depending both on the input and on the
sequence of operations used. If a given input $\sigma$ can
produce a particular output $\tau$ then $(\sigma,\tau)$ is
said to be an {\em allowable pair}. It is shown that allowable
pairs on a fixed multiset are in one-to-one correspondence
with certain k-way trees and, consequently, the allowable
pairs can be enumerated. Algorithms are presented for
determining the number of allowable pairs with a fixed input
component, or with a fixed output component. Finally,
generating functions are used to study the maximum number of
output components with a fixed input component, and a symmetry
result is derived.
\bye