×

Priority queues and multisets. (English) Zbl 0852.90075

Electron. J. Comb. 2, Research paper R24, 18 p. (1995); printed version J. Comb. 2, 385-402 (1995).
Summary: 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 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.

MSC:

90B22 Queues and service in operations research

Software:

AXIOM
Full Text: EMIS