Carleton University
Technical Report TR-205
April 1992
The Permutational Power of a Priority Queue
M.D. Atkinson & Murali Thiyagarajah
Abstract
A priority queue transforms a.n input permutation <r of some set of size n into a.n output permutation T. It is shown that the number of such pairs (u, r) is (n + 1r-1• Some related enumerative a.nd algorithmic questions a.re also considered.