The pairing heap: A new form of self-adjusting heap (Q1087333): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: DBLP publication ID (P1635): journals/algorithmica/FredmanSST86, #quickstatements; #temporary_batch_1731508824982 |
||
| (One intermediate revision by one other user not shown) | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf01840439 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2006820476 / rank | |||
Normal rank | |||
| Property / DBLP publication ID | |||
| Property / DBLP publication ID: journals/algorithmica/FredmanSST86 / rank | |||
Normal rank | |||
Latest revision as of 15:53, 13 November 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The pairing heap: A new form of self-adjusting heap |
scientific article |
Statements
The pairing heap: A new form of self-adjusting heap (English)
0 references
1986
0 references
Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called the Fibonacci 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 the pairing 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.
0 references
data structure
0 references
priority queue
0 references
Fibonacci heap
0 references
pairing heap
0 references
complexity analysis
0 references
0 references
