Bounded Capacity Priority Queues

A k-bounded priority queue transforms an input sequence sigma into an output sequence tau which is a re-ordering of the sequence sigma while never storing more than k elements during the transformation. We consider the set of all such related pairs (sigma, tau) in both the case that sigma is a binary sequence and the case that sigma is a permutation of 1,2,..., n. We derive properties of this relation and use it to describe systems of priority queues in series. In the binary case we give an efficient algorithm for computing the number of outputs achievable from a given input and the number of inputs which can give rise to a given output. Finally, we give a one-to-one correspondence between related binary input-output pairs and ordered forests of restricted height.