The pairing heap: A new form of self-adjusting heap View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-11

AUTHORS

Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan

ABSTRACT

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem. More... »

PAGES

111-129

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "EECS Department, University of California, 92093, San Diego, La Jolla, California, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "EECS Department, University of California, 92093, San Diego, La Jolla, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fredman", 
        "givenName": "Michael L.", 
        "id": "sg:person.01271420652.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271420652.77"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sedgewick", 
        "givenName": "Robert", 
        "id": "sg:person.013246327644.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013246327644.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sleator", 
        "givenName": "Daniel D.", 
        "id": "sg:person.013732646434.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732646434.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA", 
            "AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tarjan", 
        "givenName": "Robert E.", 
        "id": "sg:person.014142465473.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014142465473.44"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02579168", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009027313", 
          "https://doi.org/10.1007/bf02579168"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986-11", 
    "datePublishedReg": "1986-11-01", 
    "description": "Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01840439", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "keywords": [
      "complexity analysis", 
      "open problem", 
      "efficient form", 
      "complete analysis", 
      "form", 
      "Fibonacci heaps", 
      "theory", 
      "problem", 
      "Fredman", 
      "Tarjan", 
      "kind", 
      "new forms", 
      "analysis", 
      "heap", 
      "practice", 
      "paper", 
      "theFibonacci heap", 
      "kinds of heaps", 
      "thepairing heap", 
      "partial complexity analysis", 
      "self-adjusting heap"
    ], 
    "name": "The pairing heap: A new form of self-adjusting heap", 
    "pagination": "111-129", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024603098"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01840439"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01840439", 
      "https://app.dimensions.ai/details/publication/pub.1024603098"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_196.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01840439"
  }
]
 

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/bf01840439'

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/bf01840439'

Turtle is a human-readable linked data format.

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

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

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


 

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

110 TRIPLES      22 PREDICATES      48 URIs      39 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01840439 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N6a7f93199d814dc380cf502aae9477b9
4 schema:citation sg:pub.10.1007/bf02579168
5 schema:datePublished 1986-11
6 schema:datePublishedReg 1986-11-01
7 schema:description Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N08fa5cb9e7f24b0e886856fd62194298
12 Na5b0aaaa04334efbb491d2a6411a210d
13 sg:journal.1047644
14 schema:keywords Fibonacci heaps
15 Fredman
16 Tarjan
17 analysis
18 complete analysis
19 complexity analysis
20 efficient form
21 form
22 heap
23 kind
24 kinds of heaps
25 new forms
26 open problem
27 paper
28 partial complexity analysis
29 practice
30 problem
31 self-adjusting heap
32 theFibonacci heap
33 theory
34 thepairing heap
35 schema:name The pairing heap: A new form of self-adjusting heap
36 schema:pagination 111-129
37 schema:productId N5c8134b59a1843e589459bb41d6602ef
38 Nfe72310084b94fd59409ee73a64e966d
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024603098
40 https://doi.org/10.1007/bf01840439
41 schema:sdDatePublished 2022-01-01T18:04
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N4af075ad04f14e3cbb4eaf1fd22f5c59
44 schema:url https://doi.org/10.1007/bf01840439
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N08fa5cb9e7f24b0e886856fd62194298 schema:issueNumber 1-4
49 rdf:type schema:PublicationIssue
50 N4af075ad04f14e3cbb4eaf1fd22f5c59 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N5c8134b59a1843e589459bb41d6602ef schema:name doi
53 schema:value 10.1007/bf01840439
54 rdf:type schema:PropertyValue
55 N6a7f93199d814dc380cf502aae9477b9 rdf:first sg:person.01271420652.77
56 rdf:rest Nd5bc587b06ea4aaab1a19487931d6ba8
57 Na5b0aaaa04334efbb491d2a6411a210d schema:volumeNumber 1
58 rdf:type schema:PublicationVolume
59 Nb9eb70f069bf4c33ac01e6f894164c8d rdf:first sg:person.014142465473.44
60 rdf:rest rdf:nil
61 Nd5bc587b06ea4aaab1a19487931d6ba8 rdf:first sg:person.013246327644.91
62 rdf:rest Nf6c9559ed79046b8a565960b6b5f91f0
63 Nf6c9559ed79046b8a565960b6b5f91f0 rdf:first sg:person.013732646434.45
64 rdf:rest Nb9eb70f069bf4c33ac01e6f894164c8d
65 Nfe72310084b94fd59409ee73a64e966d schema:name dimensions_id
66 schema:value pub.1024603098
67 rdf:type schema:PropertyValue
68 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
69 schema:name Mathematical Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
72 schema:name Numerical and Computational Mathematics
73 rdf:type schema:DefinedTerm
74 sg:journal.1047644 schema:issn 0178-4617
75 1432-0541
76 schema:name Algorithmica
77 schema:publisher Springer Nature
78 rdf:type schema:Periodical
79 sg:person.01271420652.77 schema:affiliation grid-institutes:None
80 schema:familyName Fredman
81 schema:givenName Michael L.
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271420652.77
83 rdf:type schema:Person
84 sg:person.013246327644.91 schema:affiliation grid-institutes:grid.16750.35
85 schema:familyName Sedgewick
86 schema:givenName Robert
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013246327644.91
88 rdf:type schema:Person
89 sg:person.013732646434.45 schema:affiliation grid-institutes:None
90 schema:familyName Sleator
91 schema:givenName Daniel D.
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732646434.45
93 rdf:type schema:Person
94 sg:person.014142465473.44 schema:affiliation grid-institutes:None
95 schema:familyName Tarjan
96 schema:givenName Robert E.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014142465473.44
98 rdf:type schema:Person
99 sg:pub.10.1007/bf02579168 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009027313
100 https://doi.org/10.1007/bf02579168
101 rdf:type schema:CreativeWork
102 grid-institutes:None schema:alternateName AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA
103 EECS Department, University of California, 92093, San Diego, La Jolla, California, USA
104 schema:name AT & T Bell Laboratories, 07974, Murray Hill, New Jersey, USA
105 Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA
106 EECS Department, University of California, 92093, San Diego, La Jolla, California, USA
107 rdf:type schema:Organization
108 grid-institutes:grid.16750.35 schema:alternateName Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA
109 schema:name Computer Science Department, Princeton University, 08544, Princeton, New Jersey, USA
110 rdf:type schema:Organization
 




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


...