A priority queue transforms an input permutation σ of some set of size n into an output permutation τ. The set Rn of such related pairs (σ, τ) is studied. Efficient algorithms for determining s(τ) = |σ:(σ, τ) ε Rn| and t(σ) = |τ:(σ, τ) ε Rn| are given, a new proof that |Rn| = (n + 1)n-1 is given, and the transitive closure of Rn is found.
All Science Journal Classification (ASJC) codes
- Computer Science(all)