pairing heap (as a practical alternative)
E1045596
comparison-based priority queue
heap data structure
priority queue implementation
self-adjusting heap
A pairing heap is a simple, self-adjusting heap data structure that offers efficient practical performance for priority queue operations and is often used as an alternative to more complex structures like Fibonacci heaps.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| pairing heap | 0 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
comparison-based priority queue
ⓘ
heap data structure ⓘ priority queue implementation ⓘ self-adjusting heap ⓘ |
| advantageOver |
Fibonacci heap in constant factors for typical workloads
ⓘ
Fibonacci heap in implementation simplicity ⓘ |
| category |
amortized data structure
ⓘ
meldable heap ⓘ |
| comparedTo | Fibonacci heap NERFINISHED ⓘ |
| deleteMinProcess | remove minimum root and pairwise meld its children ⓘ |
| designGoal | combine simplicity with good amortized performance ⓘ |
| hasAlternativeName | pairing heap priority queue ⓘ |
| hasProperty |
amortized efficient operations
ⓘ
does not require auxiliary structural information per node ⓘ good practical performance ⓘ heap-ordered ⓘ pointer-based ⓘ self-adjusting ⓘ simple to implement ⓘ supports meldable heaps ⓘ |
| implementationDetail | usually implemented with child-sibling representation for trees ⓘ |
| introducedAs | simpler alternative to Fibonacci heap ⓘ |
| isMeldable | true ⓘ |
| linkOperation | compare two roots and make larger root a child of smaller root ⓘ |
| memoryOverhead | low compared to Fibonacci heap ⓘ |
| mergeStrategy | pairwise linking of subtrees ⓘ |
| nodeStructure | tree node with key and list of children ⓘ |
| practicalObservation | often outperforms Fibonacci heap on real workloads ⓘ |
| representation |
forest of heap-ordered trees
ⓘ
multiway tree ⓘ |
| requires | total order on keys ⓘ |
| supports | online operations ⓘ |
| supportsOperation |
decrease-key
ⓘ
delete-min ⓘ find-min ⓘ insert ⓘ meld ⓘ merge ⓘ |
| timeComplexityDecreaseKey | sub-logarithmic amortized in practice (theoretical bounds vary) ⓘ |
| timeComplexityDeleteMin | O(log n) amortized (under common analyses) ⓘ |
| timeComplexityFindMin | O(1) amortized ⓘ |
| timeComplexityInsert | O(1) amortized ⓘ |
| timeComplexityMeld | O(1) amortized ⓘ |
| typicalUseCase |
Dijkstra shortest path algorithm priority queue
ⓘ
any application needing fast decrease-key ⓘ event simulation priority queue ⓘ |
| usedAs |
implementation of priority queue abstract data type
ⓘ
practical alternative to Fibonacci heap ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.