About: Bucket queue

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Bucket queue Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FBucket_queue

A bucket queue is a data structure that implements the priority queue abstract data type: it maintains a dynamic collection of elements with numerical priorities and allows quick access to the element with minimum (or maximum) priority. In the bucket queue, the priorities must be integers, and it is particularly suited to applications in which the priorities have a small range. A bucket queue has the form of an array of buckets: an array data structure, indexed by the priorities, whose cells contain collections of items with the same priority as each other. With this data structure, insertion of elements and changes of their priority take constant time. Searching for and removing the minimum-priority element takes time proportional to the number of buckets or, by maintaining a pointer to t

Attributes	Values
rdfs:label	Bucket queue (en)
rdfs:comment	A bucket queue is a data structure that implements the priority queue abstract data type: it maintains a dynamic collection of elements with numerical priorities and allows quick access to the element with minimum (or maximum) priority. In the bucket queue, the priorities must be integers, and it is particularly suited to applications in which the priorities have a small range. A bucket queue has the form of an array of buckets: an array data structure, indexed by the priorities, whose cells contain collections of items with the same priority as each other. With this data structure, insertion of elements and changes of their priority take constant time. Searching for and removing the minimum-priority element takes time proportional to the number of buckets or, by maintaining a pointer to t (en)
name	Bucket queue (en)
foaf:depiction
dcterms:subject	Priority queues
Wikipage page ID	50988787 (xsd:integer)
Wikipage revision ID	1117403340 (xsd:integer)
Link from a Wikipage to another Wikipage	Degeneracy (graph theory) Algorithm Applied mathematics Approximation algorithm Undirected graph Degree (graph theory) Doubly linked list Dynamic array Numerical method Eikonal equation Boundary value problem NP-hard Container (abstract data type) Linear time Lower bound Calendar queue Shortest path Computer graphics Pigeonhole sort Priority queue Marching cubes Data structure Widest path problem Abstract data type Differential equation Dijkstra Directed graph Discrete-event simulation Family of sets Fast marching method Packet forwarding Quality of service Wave propagation Monotone priority queue Jagged array Priority queues Dijkstra's algorithm Donald B. Johnson Constant time Greedy algorithm Integer Bucket (computing) Real number Selection sort Set cover problem Set (abstract data type) Vertex (graph theory) Dial's algorithm Scheduling (computing) Soft heap P versus NP problem Sequential search Monotonic sequence
sameAs	Bucket queue Bucket queue Bucket queue
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Harvtxt dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Short_description dbt:Harvnb dbt:Infobox_data_structure
thumbnail	wiki-commons:Special:FilePath/GWR_Fire_Buckets,_Severn_Valley_Railway_(17351340581).jpg?width=300
caption	An array of buckets, suitable for priorities in the range from 1 to 6. The minimum-priority element can be found in the leftmost non-empty bucket. (en)
type	Priority queue
has abstract	A bucket queue is a data structure that implements the priority queue abstract data type: it maintains a dynamic collection of elements with numerical priorities and allows quick access to the element with minimum (or maximum) priority. In the bucket queue, the priorities must be integers, and it is particularly suited to applications in which the priorities have a small range. A bucket queue has the form of an array of buckets: an array data structure, indexed by the priorities, whose cells contain collections of items with the same priority as each other. With this data structure, insertion of elements and changes of their priority take constant time. Searching for and removing the minimum-priority element takes time proportional to the number of buckets or, by maintaining a pointer to the most recently found bucket, in time proportional to the difference in priorities between successive operations. The bucket queue is the priority-queue analogue of pigeonhole sort (also called bucket sort), a sorting algorithm that places elements into buckets indexed by their priorities and then concatenates the buckets. Using a bucket queue as the priority queue in a selection sort gives a form of the pigeonhole sort algorithm. Bucket queues are also called bucket priority queues or bounded-height priority queues. When used for quantized approximations to real number priorities, they are also called untidy priority queues or pseudo priority queues. They are closely related to the calendar queue, a structure that uses a similar array of buckets for exact prioritization by real numbers. Applications of the bucket queue include computation of the degeneracy of a graph, fast algorithms for shortest paths and widest paths for graphs with weights that are small integers or are already sorted, and greedy approximation algorithms for the set cover problem. The quantized version of the structure has also been applied to scheduling and to marching cubes in computer graphics. The first use of the bucket queue was in a shortest path algorithm by . (en)
invented by	Robert Dial (en)
invented year	1969 (xsd:integer)
prov:wasDerivedFrom	wikipedia-en:Bucket_queue?oldid=1117403340&ns=0
page length (characters) of wiki page	25680 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Bucket_queue
is Link from a Wikipage to another Wikipage of	Degeneracy (graph theory) Calendar queue Shortest path problem Pigeonhole sort Priority queue Widest path problem Monotone priority queue Dijkstra's algorithm Integer sorting Set cover problem
is foaf:primaryTopic of	wikipedia-en:Bucket_queue

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software