A priority queue in which initialization and queue operations takeO(loglogD) time View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1981-12

AUTHORS

Donald B. Johnson

ABSTRACT

Many computer algorithms have embedded in them a subalgorithm called a priority queue which produces on demand an element of extreme priority among elements in the queue. Queues on unrestricted priority domains have a running time of Θ(nlogn) for sequences ofn queue operations. We describe a simple priority queue over the priority domain {1,⋯,N} in which initialization, insertion, and deletion takeO(loglogD) time, whereD is the difference between the next lowest and next highest priority elements in the queue. In the case of initialization,D=Θ(N). Finding a least element, greatest element, and the neighbor in priority order of some specified element take constant time. We also consider dynamic space allocation for the data structures used. Space can be allocated in blocks of size Θ(N1/p), for small integerp. More... »

PAGES

295-309

References to SciGraph publications

  • 1976-12. Design and implementation of an efficient priority queue in MATHEMATICAL SYSTEMS THEORY
  • 1975-12. Analysis of an algorithm for priority queue administration in BIT NUMERICAL MATHEMATICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01786986

    DOI

    http://dx.doi.org/10.1007/bf01786986

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1043049777


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Pennsylvania State University", 
              "id": "https://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Department of Computer Science, The Pennsylvania State University, University Park, Pennsylvania, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Johnson", 
            "givenName": "Donald B.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0020-0190(75)90001-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004350160"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321992.321993", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005748205"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(77)90031-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029510709"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01931680", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051805622", 
              "https://doi.org/10.1007/bf01931680"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053048814", 
              "https://doi.org/10.1007/bf01683268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053048814", 
              "https://doi.org/10.1007/bf01683268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0207026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841420"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1975.26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086220655"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1981-12", 
        "datePublishedReg": "1981-12-01", 
        "description": "Many computer algorithms have embedded in them a subalgorithm called a priority queue which produces on demand an element of extreme priority among elements in the queue. Queues on unrestricted priority domains have a running time of \u0398(nlogn) for sequences ofn queue operations. We describe a simple priority queue over the priority domain {1,\u22ef,N} in which initialization, insertion, and deletion takeO(loglogD) time, whereD is the difference between the next lowest and next highest priority elements in the queue. In the case of initialization,D=\u0398(N). Finding a least element, greatest element, and the neighbor in priority order of some specified element take constant time. We also consider dynamic space allocation for the data structures used. Space can be allocated in blocks of size \u0398(N1/p), for small integerp.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01786986", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1317508", 
            "issn": [
              "0025-5661"
            ], 
            "name": "Mathematical Systems Theory", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "15"
          }
        ], 
        "name": "A priority queue in which initialization and queue operations takeO(loglogD) time", 
        "pagination": "295-309", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "cd0f81dc23946c6dd75b6b84239e50b60959ad31dcb47a2335adc272ae03408b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01786986"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1043049777"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01786986", 
          "https://app.dimensions.ai/details/publication/pub.1043049777"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:51", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000347_0000000347/records_89789_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01786986"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01786986'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01786986'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01786986'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01786986'


     

    This table displays all metadata directly associated to this object as RDF triples.

    82 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01786986 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nb8cc52bbafbb40f490b21c2b4a3c234c
    4 schema:citation sg:pub.10.1007/bf01683268
    5 sg:pub.10.1007/bf01931680
    6 https://doi.org/10.1016/0020-0190(75)90001-0
    7 https://doi.org/10.1016/0020-0190(77)90031-x
    8 https://doi.org/10.1109/sfcs.1975.26
    9 https://doi.org/10.1137/0207026
    10 https://doi.org/10.1145/321992.321993
    11 schema:datePublished 1981-12
    12 schema:datePublishedReg 1981-12-01
    13 schema:description Many computer algorithms have embedded in them a subalgorithm called a priority queue which produces on demand an element of extreme priority among elements in the queue. Queues on unrestricted priority domains have a running time of Θ(nlogn) for sequences ofn queue operations. We describe a simple priority queue over the priority domain {1,⋯,N} in which initialization, insertion, and deletion takeO(loglogD) time, whereD is the difference between the next lowest and next highest priority elements in the queue. In the case of initialization,D=Θ(N). Finding a least element, greatest element, and the neighbor in priority order of some specified element take constant time. We also consider dynamic space allocation for the data structures used. Space can be allocated in blocks of size Θ(N1/p), for small integerp.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf Nf690acf27b6342c6a517989ef9022e10
    18 Nfebeed9898b04cd3a7fb8aa5b5aeb096
    19 sg:journal.1317508
    20 schema:name A priority queue in which initialization and queue operations takeO(loglogD) time
    21 schema:pagination 295-309
    22 schema:productId N32b487dcce1a4c209fe017c3f4e5d4af
    23 Ncc62b260cbb74b87be7bb695a93c1dc1
    24 Nf7bc5ac4cf094480a2b5adc098711e61
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043049777
    26 https://doi.org/10.1007/bf01786986
    27 schema:sdDatePublished 2019-04-11T09:51
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N908f86d7f0304a41bd3e39011f59354c
    30 schema:url http://link.springer.com/10.1007/BF01786986
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N32b487dcce1a4c209fe017c3f4e5d4af schema:name doi
    35 schema:value 10.1007/bf01786986
    36 rdf:type schema:PropertyValue
    37 N54818a2a10af47afb0a54bbdd91d89b8 schema:affiliation https://www.grid.ac/institutes/grid.29857.31
    38 schema:familyName Johnson
    39 schema:givenName Donald B.
    40 rdf:type schema:Person
    41 N908f86d7f0304a41bd3e39011f59354c schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 Nb8cc52bbafbb40f490b21c2b4a3c234c rdf:first N54818a2a10af47afb0a54bbdd91d89b8
    44 rdf:rest rdf:nil
    45 Ncc62b260cbb74b87be7bb695a93c1dc1 schema:name dimensions_id
    46 schema:value pub.1043049777
    47 rdf:type schema:PropertyValue
    48 Nf690acf27b6342c6a517989ef9022e10 schema:issueNumber 1
    49 rdf:type schema:PublicationIssue
    50 Nf7bc5ac4cf094480a2b5adc098711e61 schema:name readcube_id
    51 schema:value cd0f81dc23946c6dd75b6b84239e50b60959ad31dcb47a2335adc272ae03408b
    52 rdf:type schema:PropertyValue
    53 Nfebeed9898b04cd3a7fb8aa5b5aeb096 schema:volumeNumber 15
    54 rdf:type schema:PublicationVolume
    55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Information and Computing Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Artificial Intelligence and Image Processing
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1317508 schema:issn 0025-5661
    62 schema:name Mathematical Systems Theory
    63 rdf:type schema:Periodical
    64 sg:pub.10.1007/bf01683268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053048814
    65 https://doi.org/10.1007/bf01683268
    66 rdf:type schema:CreativeWork
    67 sg:pub.10.1007/bf01931680 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051805622
    68 https://doi.org/10.1007/bf01931680
    69 rdf:type schema:CreativeWork
    70 https://doi.org/10.1016/0020-0190(75)90001-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004350160
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1016/0020-0190(77)90031-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1029510709
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1109/sfcs.1975.26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086220655
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1137/0207026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841420
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1145/321992.321993 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005748205
    79 rdf:type schema:CreativeWork
    80 https://www.grid.ac/institutes/grid.29857.31 schema:alternateName Pennsylvania State University
    81 schema:name Department of Computer Science, The Pennsylvania State University, University Park, Pennsylvania, USA
    82 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...