The pairing heap: A new form of self-adjusting heap

DOI10.1007/BF01840439zbMath0611.68042DBLPjournals/algorithmica/FredmanSST86OpenAlexW2006820476WikidataQ56210997 ScholiaQ56210997MaRDI QIDQ1087333

B. George

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840439

zbMATH Keywords

priority queuecomplexity analysisdata structureFibonacci heappairing heap

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (37)

Replacing Mark Bits with Randomness in Fibonacci Heaps ⋮ Fast meldable priority queues ⋮ The K-D heap: An efficient multi-dimensional priority queue ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ A complexity O(1) priority queue for event driven molecular dynamics simulations ⋮ Proximate point searching ⋮ Amortized Complexity Verified ⋮ The weak-heap data structure: variants and applications ⋮ A priority queue with the time-finger property ⋮ A Linear Potential Function for Pairing Heaps ⋮ Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees ⋮ Unnamed Item ⋮ Optimal purely functional priority queues ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ The saga of minimum spanning trees ⋮ Two-tier relaxed heaps ⋮ Pairing heaps: the forward variant. ⋮ Three priority queue applications revisited ⋮ Amortized complexity verified ⋮ A generalization of binomial queues ⋮ Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN ⋮ STRONGER QUICKHEAPS ⋮ A SIMPLE ARRAY VERSION OF M-HEAP ⋮ A systematic analysis of splaying ⋮ On sorting, heaps, and minimum spanning trees ⋮ Blossom V: A new implementation of a minimum cost perfect matching algorithm ⋮ Priority queues on parallel machines ⋮ The number of tests required to search an unordered table ⋮ THE VIOLATION HEAP: A RELAXED FIBONACCI-LIKE HEAP ⋮ The derivation of a tighter bound for top-down skew heaps ⋮ Progressive simplification of polygonal curves ⋮ A tight amortized bound for path reversal ⋮ Quake Heaps: A Simple Alternative to Fibonacci Heaps ⋮ A Survey on Priority Queues ⋮ A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY ⋮ Regarding Goal Bounding and Jump Point Search ⋮ The relaxed min-max heap: A mergeable double-ended priority queue

Uses Software

• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Amortized Computational Complexity
• Self-adjusting binary search trees
• A data structure for manipulating priority queues
• Implementation and Analysis of Binomial Queue Algorithms
• Self-Adjusting Heaps
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: The pairing heap: A new form of self-adjusting heap