Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Priority Queues and Multisets. | Priority Queues and Multisets . Atkinson . Linton . Walker Department of Mathematical and Computational Sciences University of St. Andrews North Haugh St. Andrews KY16 9SS Scotland sal mda louise @ Submitted February 14 1995 Accepted November 10 1995. 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 T then a T 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. Mathematical Reviews Subject Classifications 68R05 05A15 68P05 1 Introduction Abstract data types ADTs are a fundamental design tool in modern software systems. They are setting the direction of programming in the 1980 s and 1990 s as firmly as Structured Programming set it in the 1960 s and 1970 s. In principle there is an infinity of possible ADTs since an ADT is defined once its permitted set of operations has been specified and there is no restriction on this set except for common sense. In practice a small number of ADTs occur over and over again stacks arrays queues dictionaries etc. suggesting that some ADTs are more natural than others. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R24 2 Exactly the same phenomenon occurs in algebra and significantly the natural algebraic systems groups rings modules etc. have very rich theories. Many of the commonly occurring ADTs are container data types they are holders for collections of data items
