PRIORITY-QUEUES AND PERMUTATIONS

A priority queue transforms an input permutation a of some set of size n into an output permutation tau. The set R(n) of such related pairs (sigma, tau) is studied. Efficient algorithms for determining s(tau) = \sigma : (sigma,tau) epsilon R(n)/ and t (sigma) = \tau : (sigma,tau) epsilon R(n)\ are given, a new proof that \R(n)\ = (n + 1)(n-1) is given, and the transitive closure of R(n) is found.