Priority queues and permutations

M. D. Atkinson, Robert Beals

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1225-1230
Number of pages6
JournalSIAM Journal on Computing
Volume23
Issue number6
DOIs
StatePublished - Jan 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Priority queues and permutations'. Together they form a unique fingerprint.

Cite this