Priority queues and multisets

Priority queues and multisets

0.00 Avg rating0 Votes
Article ID: iaor20023055
Country: United States
Volume: 2
Issue: 1
Publication Date: Jan 1995
Journal: Electronic Journal of Combinatorics
Authors: , ,
Keywords: sets
Abstract:

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 σ can produce a particular output τ then (σ,τ) 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.

Reviews

Required fields are marked *. Your email address will not be published.