Priority queues and multisets
type: Item
instance of: scholarly article
title: Priority queues and multisets
zbMATH Open document ID: 0852.90075
author: Yanyan Li
published in: The Electronic Journal of Combinatorics
publication date: 1996-07-21T00:00:00Z
full work available at URL: R24
review text: Summary: A priority queue, a container data structure equipped with the operations insert and delete-minimum, can re-order its input in various ways, depending both on the input and on the sequence of operations used. If a given input \(\sigma\) can produce a particular output \(\tau\) then \((\sigma, \tau)\) is said to be an allowable pair. It is shown that allowable pairs on a fixed multiset are in one-to-one correspondence with certain \(k\)-way trees and, consequently, the allowable pairs can be enumerated. Algorithms are presented for determining the number of allowable pairs with a fixed input component, or with a fixed output component. Finally, generating functions are used to study the maximum number of output components with a fixed input component, and a symmetry result is derived.
Mathematics Subject Classification ID: 90B22
zbMATH DE Number: 861584
zbMATH Keywords: priority queue
zbMATH Keywords: allowable pairs on a fixed multiset
describes a project that uses: AXIOM
MaRDI profile type: Publication
Recommended article: Priority queues
Recommended article: Multipartite priority queues
Recommended article: Priority Queues and Permutations
Recommended article: Q4737156
Recommended article: Q4025154
Recommended article: Rank-Sensitive Priority Queues
Recommended article: Priority Queues with Setup Times
Recommended article: Buckets, Heaps, Lists, and Monotone Priority Queues
Recommended article: A Survey on Priority Queues
Recommended article: Priority queues with binary priorities
description: scientific article; zbMATH DE number 861584