| Related sites for http://www.leekillough.com/heaps/ |
| Tree_Automata_Techniques_and_Applications An evolving web text in PostScript and PDF, with related software. | | Web_Data_Structures_and_Algorithms Lecture notes and links for a course by Godfried Toussaint. | | European_Multimedia_Forum_(EMF) The main European trade association promoting the competitiveness of the digital media industries in the global market place. | | Issues_in_Multimedia_Authoring Information about authoring metaphors, content design, visual design and technical design. | | Media_Mall Includes digital media related news, articles and reviews, covering software, hardware and general multimedia. | | Multimedia_Authoring_Guidelines Recommendations on how to use multimedia for teaching and learning, taking a project management approach to multimedia development. | | Multimedia_Authoring_Web Links and searchable resources for multimedia authors and developers. Site has ceased being updated so acts now as an archive of links. | | The_Multimedia_Library_Gazette Collection of articles, resources, and media for developers. | | Multimedia/Hypermedia Gallery of multimedia content. Features ASCII art, audio, background images, clipart, maps, MOD soundtracks, and Quicktime video clips. | | Scala_Multimedia_Directory Index to various types of multimedia resources, including articles, software, authorities, samples. | | Altair32 An open source Altair emulator for Windows. | | blueMSX An open source SVI318/328, MSX1, MSX2, MSX2+, and Turbo-R emulator for Windows. | | Chip-8_Emulator A freeware Chip-8 emulator for DOS. | | cinc An open source Bell Labs cardiac emulator for Linux and Windows/Cygwin. | | CP/M An open source CP/M-80 ver2.2 emulator for MacOS. | | Desktop_Cyber An open source CDC (Control Data Corporation) Cyber 6x00, 7x or 17x type mainframe emulator for Windows or Unix. | | Emu28 An open source HP18C/28C emulator for Windows. | | Emu51 An open source 8051 emulator for Linux and Windows. | | Emula3 Contains emulators for many different computers and calculators/PDAs for many different platforms. [English/Italian] | | Emuviews Great emulation page maintained by JoseQ, maker of the famous Rumor Mill, many downloads, great layout - some hosted sites. | | Evenson_Consulting_Services\'_SWTPc_6800/6809_Emulator Windows 9x/NT GUI emulation of SWTPc 6800 and 6809 systems. A Simulated Machine Environment (SME) emulation plus .dsk file downloads. | | Flexemu An open source EurocomII/V7 emulator for Linux and Windows. | | FunnyMu A freeware Creativision, Funvision, and Whizzard emulator for Linux/SDL. | | GXemul An open source MIPS machine emulator for Linux. | | HiRISC_Simulator A freeware emulator for Windows of a system designed specifically for the Applied Systems Programming course at the University of Akron. | | James_the_Animal_Tamer\'s_Emulators Freeware APF, Aquarius, Exidy Sorcerer, Interact Family Computer, MC-10, NEC PC-6001A, Panasonic Personal Computer, and TRS-80 emulators for Windows. | | Japanese_Computer_Emulation_Centre A site dedicated to the emulation of Japanese Machines including X68000, PC6001, PC88, PC98, MSX 1/2/R, Sharp MZ, Sharp X1, Fujitsu FM7, and Fujitsu FM Towns. | | KCemu An open source emulator of the KC85 homecomputer series for Linux and Windows. | | mic1 A Java-based simulator which implements the Mic-1 microarchitecture described in Chapter 4 of Andrew S. Tanenbaum, Structured Computer Organization, Fourth Edition. [Open source, GPL] | | Newbrain_Emulator_Pro A freeware Grundy NewBrain emulator for Windows written in Delphi. | | PearPC An open source PowerPC emulator for Unix and Windows. | | Project8080 Covers the development of a Heathkit H8 emulator on Macintosh. | | SIMH An open source collection of emulators for Windows of historical computers, including GRI-909, HP 2116/2100/21MX, IBM 1401/1620/1130/System 3, PDP-1/4/7-11/15/VAX. Also provides software kits, system | | Solace An open source Sol-20 emulator for Windows. | | SPRINT A freeware Sprinter emulator for Linux/i386 and Windows. | | st20emu A freeware ST20 emulator for DOS. | | The_Susie_V_pages A freeware BCL Susie V emulator for Linux/i386. | | TinyELF A freeware emulator of CDP1802 based microcomputers for Mac OS X. | | Virtual_Alpha_Micro An open source AM-100 micro computer emulator for Cygwin, Linux, and Mac OSX. | | vmips An open source MIPS R3000 emulator for Unix. |
|
Priority QueuesPriority Queues By Lee Killough If links are broken, please look here for papers. I have not had time to update links. ContentsIntroductory MaterialPriority Queue Starting PointsPapers on Priority QueuesPriority Queue ImplementationsTopics Related to Priority QueuesHeap StatisticsPriority Queues SurveyAbout This PagePages which refer to this oneGlossaryIntroductory MaterialDefinitions of Algorithms, Data Structures, and ProblemsDefinition of priority queue and related terms, in Paul Black's computer science glossary Heaps (Priority Queues) Ian Graham's lecture HeapsStefan Xenos' survey of priority queues and their complexities Data Structures and Algorithms: QueuesJohn Morris' notes on priority queues Data StructuresIntroduction to data structures, with Java code, by Peter M. Williams Heaps and Priority QueuesOnline chapter of Data Structures and Algorithms with Object-Oriented Design Patterns in C++, by Bruno R. Preiss Priority Queues and HeapsortIntroduction to heaps using tournaments, by Steven S. Skiena Priority QueuesIntroduction to priority queues, including k-heaps, Leftist heaps, and binomial queues, by Barry Kurtz Data Structures in C++ Case Study: Priority QueuesTimothy Colburn's lecture slides on priority queues Priority Queues and Heaps Introduction to priority queues and heapsort, with C code The Complete Collection of Algorithm Animations Pointers to online animations of algorithms and data structuresA Priority Queue Tester A Java demonstration of priority queue insertion and removalStarting PointsIf you're just looking for the fastest priority queue for an application,or if you want a survey of the different kinds of priority queues and theirstrengths and weaknesses, I recommend you first read the following:* Indicates access may be restricted Rassul AyaniA comparative study of parallel and sequential priority queue algorithms,with Robert RönngrenRolf FagerbergA Note on Worst Case Efficient Meldable Priority Queues AbstractDouglas W. JonesAn Empirical Comparison of Priority-Queue and Event-Set Implementations* ReviewAndrew V. GoldbergBuckets, Heaps, Lists, and Monotone Priority Queues, withBoris V. Cherkassky and Craig Silverstein Abstract older version SoftwareHeap-on-Top Priority Queues, withBoris V. Cherkassky and Craig Silverstein AbstractAnthony LaMarcaThe Influence of Caches on the Performance of Heaps,with Richard E. Ladner AbstractMauricio MarínOn the Pending Event Set and Binary TournamentsAn Empirical Comparison of Priority Queue Algorithms Bernard M.E. Moret, H.D. ShapiroAlgorithms From P to NP: Design and Efficiency,pp. 130-187SoftwarePapers on Priority QueuesArranged alphabetically by author. Hyperlinks under the authors' names, arelinks to their personal home pages.ABCDEFGHIJKLMNOPQRSTUVWXYZ* Indicates access may be restrictedSantosh G. AbrahamSee Rabin A. SugumarArne AnderssonSee Mikkel ThorupMike D. AtkinsonPriority Queues and MultisetsHTMLPriority Queues and Permutations AbstractMin-max heaps and generalized priority queues*,withJörg-Rüdiger SackNicola Santoro, Thomas Strothotte ReviewRassul Ayani (on leave)A comparative study of parallel and sequential priority queue algorithms, with Robert Rönngren AbstractLazy Queue: A new approach to implementation of the pending-event set,with J. Riboe and Robert RönngrenA ComparativeStudy of Some Priority Queues Suitable For Implementation of the Pending Event Set, withJ. Riboe and Robert RönngrenEfficientImplementation of Event Sets in Time Warp, withRobert Rönngren,Samir R. Das and Richard M. Fujimoto AbstractLR-algorithm: Concurrent Operations on Priority QueuesArmin BäumkerSee Friedhelm Meyer auf der HeideGreg BarnesWait-Free Algorithms for HeapsRicardo Baeza-YatesSee Mauricio Marín Stacey R. BerkowitzSee Ben Shaby Jesper BojesenHeap Implementations and VariationsPerformance Engineering Case Study: Heap Construction,with Maz Spork andJyrki Juhani KatajainenJoan BoyarSee Rolf FagerbergJ.D. BrightSee Gregory F. SullivanGerth Stølting Brodal(for abstracts or related work, refer to publications page)Funnel Heap - A Cache Oblivious Priority Queue,with Rolf Fagerberg SlidesWorst-Case Efficient External-Memory Priority Queues, withJyrki Juhani Katajainen Condensed versionComparator Networks for Binary Heap Construction, withMaria Cristina Pinotti Other VersionA Parallel Priority Queue with Constant Time Operations, withChristos D. Zaroliagis,Jesper Larsson TräffOther versions:A Parallel Priority Data Structure with ApplicationsA Parallel Priority Queue with Constant Update TimeMPI InformatikWorst Case Efficient Data Structures(thesis)The Randomized Complexity of Maintaining the Minimum, withShiva Chaudhuri, Jaikumar RadhakrishnanOptimal Purely Functional Priority Queueswith Chris Okasaki SoftwarePriority Queues on Parallel MachinesWorst-Case Efficient Priority QueuesFast Meldable Priority QueuesMark Robbin BrownThe analysis of a practical and nearly optimal priority queueAbstractRandy BrownCalendar Queues: A Fast O(1) Priority Queue Implementation For the Simulation Event Set ProblemRobert J. BrownAn Efficient Algorithm for Very Large Priority QueuesAdam L. BuchsbaumData-Structural Bootstrapping and Catenable Deques (thesis)DataStructural Bootstrapping, Linear Path Compression,and Catenable Heap Ordered Double Ended Queues, withRajamani Sundar and R.E. TarjanSvante CarlssonSee Jingsen ChenBernand ChazelleThe Soft Heap: An Approximate Priority Queue with Optimal Error RateJingsen ChenThe Complexity of Heaps*,with Svante Carlsson AbstractAn efficient construction algorithm for a class of implicit double-ended priority queuesParallel heap construction using multiple selectionShenfeng ChenUsing Difficulty of Prediction toDecrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs,with John H. ReifBoris V. CherkasskySee Andrew V. GoldbergSeonghun Cho, with Sartaj SahniMergeable Double-Ended Priority Queues AbstractWeight Biased Leftist Trees and Modified Skip Lists AbstractChris ClackAndreas CrauserEfficient Priority Queues in External Memory, withPaolo Ferragina and Ulrich Meyer MirrorVan-Dat CungAn Efficient Implementation of Parallel A*, withBertrand Le CunThe Outcome of a Know-how: a Branch-and-Bound Library, withBertrand Le Cun,Catherine Roucairol,Salah DowajiSajal K. DasOptimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes,with Maria Cristina Pinottiand Falguni Sarkar AbstractDistributed Priority Queues on Hypercube Architectures,with Maria Cristina Pinottiand Falguni SarkarParallel and Distributed Meldable Priority Queues Basedon Binomial Heaps,with Maria Cristina Pinottiand Vincenzo A. CrupiEtienne DepritParallelism and Locality in Priority Queues, withSzu-Tsung Cheng,Jeff A. Jones, Abhiram Ranade, Sun-Inn Shih AbstractPaul F. DietzHeap Construction in the Parallel Comparison Tree ModelVery Fast Optimal Algorithms for Heap ConstructionYuzheng DingSee Mark Allen WeissWolfgang DittrichSee Friedhelm Meyer auf der HeideBrandon DixonMinimum Spanning Tree Verification, Fast Priority Queues, and Massively Parallel Factoring(thesis)Stefan EdelkampImplementing HEAPSORT with n log n - 0.9n and QUICKSORT with n log n + 0.2n Comparisons, with Patrick StiegelerOn the Performance of WEAK-HEAPSORTWeak-Heapsort(German) (Thesis)Rolf FagerbergA Generalization of Binomial Queues AbstractA Note on Worst Case Efficient Meldable Priority Queues AbstractAmortization Results for Chromatic Search Trees, with an Application to Priority Queues,with Kim Larsen andJoan Boyar Abstractformerly Chromatic Priority Queues AbstractPaolo FerraginaSee Andreas CrauserMichael J. FischerFishspear: A Priority Queue Algorithm*,withMichael S. Paterson Abstract ReviewRudolf FleischerA tight lower bound for the worst case of bottom-up-heapsort AbstractA simple balanced search tree with O(1) worst-case update time AbstractG.N. FredericksonMichael L. FredmanPairing Heaps are Suboptimal AbstractOn the efficiency of pairing heaps and related data structures* AbstractInformation Theoretic Implications for Pairing Heaps*Fibonacci heaps and their uses in improved network optimization algorithms*,with R.E. Tarjan ReviewHarold N. GabowAlexandros V. GerbessiotisPublicationsSelection on the Bulk-Synchronous Parallel model with applications to priority queues,with Constantinos J. SiniolakisConcurrent Heaps on the BSP modelParallel priority queue and list contraction: The BSP approach,with Constantinos J. Siniolakisand Alexandre Tiskin CAAI version Andrew V. GoldbergExpected Performance of Dijkstra's Shortest Path Algorithm,with R.E. Tarjan AbstractComputational Evaluation of Hot Queues, withCraig Silverstein AbstractBuckets, Heaps, Lists, and Monotone Priority Queues, withBoris V. Cherkassky and Craig Silverstein older version Abstract SoftwareHeap-on-Top Priority Queues, withBoris V. Cherkassky and Craig Silverstein AbstractGaston H. GonnetJ.M. de Graaf See Walter A. KostersMiltos GrammatikakisPriority Queues and Sorting for Parallel Simulation, withStefan LiescheWas Parallel Priority Queues on Cray T3E AbstractAjay GuptaLoad Balanced Priority Queues on Distributed Memory MachinesPeter HøyerA General Technique for Implementation of Efficient Priority Queues Condensed version ReviewXiaobo HuFast and efficient operations on parallel priority queues, with D.Z. ChenTimothy C.K. HuiImproving the Efficiency of the PES Structure In Discrete EventSimulations (thesis)Industrial reportFELT: A Far Future Event List Structure Optimized for Calendar QueuesGalen C. HuntSee Michael L. ScottHsien-Kuei HwangOn the number of heapsTheodore JohnsonA Highly Concurrent Priority Queue Based on the B-link Tree AbstractA Prioritized Multiprocessor Spin Lockwith Krishna Harathi AbstractArne T. JonassenThe stationary p-tree forest AbstractDouglas W. JonesSimulation Pending-Event-Set ImplementationsA generalized hold model*,with Chien-Chun Chou, Steven C. Bruell, Wen ZhangAn Empirical Comparison of Priority-Queue and Event-Set Implementations* ReviewConcurrent operations on priority queues* ReviewRolf KarlssonJyrki Juhani KatajainenMethodological issues in algorithm experimentation: a case study of heapsPerformance Engineering Case Study: Heap Construction,with Maz Spork andJesper BojesenExternal heaps combined with effective buffering,withRamzi Fadel,Kim V. Jakobsen,Jukka TeuholaWorst-Case Efficient External-Memory Priority Queues, withGerth Stølting Brodal Condensed versionThe Ultimate HeapsortDavid J. KingFunctional Binomial Queues AbstractJeffrey H. KingstonAre Fibonacci Heaps Optimal?, with Diab AbuaiadhJochen KönemannRadix heaps, an efficient implementation for priority queues, withChristoph SchmitzandChristian Schwarz AbstractWalter A. KostersTriangular Heaps, withJ.M. de GraafExpected Heights in Heaps, withJ.M. de GraafHeap BibliographyAlan T. KrantzAnalysis of an efficient algorithm for the hard-sphere problem* AbstractVipin KumarConcurrent Access of Priority Queues,withV. Nageshwara RaoParallel Processing of Discrete Optimization Problems, withAnanth Y. Grama andPanos M. Pardalos AbstractParallel Best-First Search of State-Space Graphs: A Summary of Results, withK. RameshandV. Nageshwara RaoChristopher Lee KuszmaulEfficient Merge and Insert Operations for Binary HeapsAbstractRichard E. LadnerSee Anthony LaMarcaAnthony LaMarcaThe Influence of Caches on the Performance of Heaps,with Richard E. Ladner AbstractOptimizing Static Calendar Queues,with Richard E. Ladner and K. B. Erickson AbstractThe Influence of Caches on the Performance of Sorting,with Richard E. Ladner Preliminary versionSimon LamSee Geoffrey G. XieKim Skak LarsenSee Rolf FagerbergBertrand Le CunSee Van-Dat CungJörg LiebeherrPriority Queue Schedulers with Approximate Sorting in Output Buffered Switches,with Dallas Wrege AbstractWalter LuhA Heap Based Priority Queue,with Edward LiBernard MansPortable Distributed Priority Queues with MPIMauricio MarínDiscrete-Event Simulation on the Bulk-Synchronous Parallel Model (thesis)An Empirical Assessment of Optimistic PDES on BSPBinary Tournaments and Priority Queues: PRAM and BSPDirect BSP Algorithms for Parallel Discrete-Event SimulationOn the Pending Event Set and Binary TournamentsAn Empirical Comparison of Priority Queue AlgorithmsPriority Queue Operations on EREW-PRAMBilliards and Related Systems On The Bulk Synchronous Parallel ModelHashing-Cell Combination for Boundless Space Event-Driven Molecular DynamicsAn Object Oriented C++ Approach for Discrete Event Simulation of Complex and Large Systems of Many Moving ObjectsAn Event-Driven Simulation Environmment for Hard Particle Molecular DynamicsA New Priority Queue for Simulation of Many Objects,with Ricardo Baeza-Yatesand Patricio Cordero DraftMolecular Dynamics and Kinetic Theory GroupYossi MatiasApproximate Data Structures with Applications,withJeffrey S. VitterandNeal E. Young Abstract & ThumbnailPerformance evaluation of approximate priority queues, withSuleyman Cenk SahinalpandNeal E. YoungAlessandro MeiSee Alan BertossiFriedhelm Meyer auf der HeidePriority Queue Operations and Selection for the BSP* Model, withArmin Bäumker,Wolfgang Dittrich,Ingo Rieping AbstractEuro-Par '96Ulrich Carsten MeyerSee Andreas CrauserMaged M. MichaelSee Michael L. ScottSimon W. MooreTagged up/down sorter -- A hardware priority queue,with Brian T. Graham AbstractBernard M.E. MoretAlgorithms From P to NP: Design and Efficiency,with H.D. ShapiroSoftwareJainendra K. NavlakhaThe Distribution of Keys In a Binary Heap, with M.A. WeissFinding the k-th largest element in a large heap in O(k log log n) timeBengt Julio NilssonChris OkasakiSee Gerth Stølting BrodalStephan OlariuOptimal Parallel Initialization Algorithm fora Class of Priority Queues, with Zhaofang WenIan ParberryLoad Sharing With Parallel Priority Queues AbstractSrinivasan ParthasarathySee Michael L. ScottMichael S. PatersonSee M.J. FischerStephane PerezPriority TreesMaria Cristina PinottiSee Sajal K. DasPatricio V. PobleteThomas PorterRandom insertion into a priority queue structure, withIstvan Simon AbstractSushil K. PrasadParallel Heap: A Practical Priority Queue For Fine-to-Medium GrainedApplications on Small Multiprocessors,with Sagar I. SawantHelmut ProdingerAverage Case-Analysis of Priority trees: A structure for priority queue administration AbstractDescendants in heap ordered trees or a triumph of computer algebra AbstractThe level of nodes in heap ordered trees AbstractDepth and path length of heap ordered trees AbstractRajeev RamanEliminating Amortization: On Data Structures with Guaranteed Response TimeJohn H. ReifSee Shenfeng ChenIngo RiepingSee Friedhelm Meyer auf der HeideRobert RönngrenSee Rassul AyaniJörg-Rüdiger SackSee Mike D. AtkinsonSuleyman Cenk SahinalpSee Yossi MatiasSartaj SahniSee Seonghun ChoNicola SantoroSee Mike D. AtkinsonPeter Sanders Old PageFast Priority Queues for Cached Memory Condensed ALENEX version SoftwareRandomized Priority Queues for Fast Parallel Access Expanded VersionFast priority queues for parallel branch-and-boundFlaschenhalsfreie parallele Priority queuesFalguni SarkarSee Sajal K. DasBerry SchoenmakersData Structures and Amortized Complexity in a Functional Setting (thesis)A Tight Lower Bound for Top-Down Skew Heaps AbstractA Systematic Analysis of Splaying AbstractInorder Traversal of a Binary Heap and its Inversion in Optimal Time and Space AbstractThe Derivation of a Tighter Bound for Top-Down Skew Heaps, with Anne Kaldewaij AbstractMichael L. ScottEfficient Algorithm for Concurrent Priority Queue Heaps,with Galen C. Hunt, Maged M. Michael, Srinivasan Parthasarathy Abstract PseudocodeSimple, fast, and practical non-blocking and blocking concurrent queue algorithms HTML Software ACM Proc.*Ben ShabyUnix Scheduler Implemented With a Pairing Heap, withStacey R. BerkowitzHenry D. ShapiroSee Bernard M.E. MoretNir Shavit TOC pageScalable Concurrent Priority Queues,with Asaph ZemachCraig SilversteinSee Andrew GoldbergRahul SimhaFast data structures for shortest path routing: a comparative evaluation,with G. OberhauserConstantinos J. SiniolakisSee Alex V. GerbessiotisD.D. SleatorMaz SporkDesign and Analysis of Cache-Conscious Programs (Thesis)Performance Engineering Case Study: Heap Construction,withJyrki Juhani Katajainen andJesper BojesenJohn T. StaskoTidy Animations of Tree Algorithms,with Carlton Reid TurnerDo algorithm animations assist learning?: an empirical study and analysis*, withAlbert Badre and Clayton Lewis AbstractPairing Heaps: Experiments and Analysis*, withJeffrey S. VitterJørgen StaunstrupThe priority queue as an example of hardware/software codesign,with Niels Mellergaard, Flemming HøegJeffrey S. SteinmanThe SPEEDES Qheap: A Priority-Queue Data StructureSPEEDES IntroductionDiscrete-Event Simulation and the Event Horizon* AbstractDiscrete-Event Simulation and the Event Horizon Part 2: Event List Management* AbstractUS5850538: Priority Queues for Computer SimulationsRabin A. SugumarEfficient Simulation of Multiple Cache Configurations using Binomial Trees, withSantosh G. AbrahamGregory F. SullivanChecking Mergeable Priority Queues,with J.D. BrightOn-Line Error Monitoring for Several Data Structures,with J.D. Bright AbstractBjörn von SydowDependently typed binomial queuesTadao TakaokaShortest Path Algorithms for Nearly Acyclic Directed GraphsTheory of 2-3 HeapsTheory of Trinomial HeapsR.E. Tarjan InterTrustDesign and analysis of a data structure for representing sorted lists, with Mark R. Brown AbstractJukka TeuholaSee Jyrki Juhani KatajainenMikkel ThorupTight(er) Worst-case Bounds on Dynamic Searching and Priority Queues, with Arne Andersson AbstractFaster deterministic sorting and priority queues in linear space AbstractA pragmatic implementation of monotone priority queues, with Arne AnderssonOn RAM Priority QueuesEquivalence Between Sorting and Priority QueuesAlexandre TiskinSee Alex V. GerbessiotisPeter van Emde BoasAn O(n log logn) On-line Algorithm for the Insert-Extract Min Problem AbstractSriranga VeeraraghavanA Heap Based Priority QueueJeffrey S. VitterSee Yossi Matias, John StaskoJean E. VuilleminA data structure for manipulating priority queuesMark Allen WeissThe Relaxed Min-Max Heap: A Mergeable Double-Ended Priority Queue, with Y. DingThe k-d Heap: An EfficientMulti-Dimensional Priority Queue, with Y. DingThe Distribution of Keys In a Binary Heap,with J.K. NavlakhaMike WozniewskiPriority Queues and the van Emde Boas ImplementationDallas E. WregeSee Jörg LiebeherrGeoffrey G. XieAn Efficient Adaptive Search Algorithm for Scheduling Real-Time Traffic, with Simon S. Lam AbstractNeal E. YoungSee Yossi MatiasLixin YuA Survey on Parallel Algorithms for Priority QueuesRodger ZannyEfficiency of Distributed Priority Queues in Parallel Adaptive Integration(Thesis) Abstract HTML* Indicates access may be restrictedImplementationsPriority QueuesANSI C implementation and tutorial, by Georg Kraml LEDALibrary of Efficient Data Structures and Algorithms Simulation Pending Event Set Implementations Doug Jones' splay tree and other priority queue implementations Selection AlgorithmsIn Handbook of Algorithms and Data Structures Memory Structures Library (MemSL) for C and C++Memory Structures Library (MemSL) for C and C++ SimPack/Sim++ Simulation ToolkitC++ implementations, as a "starting point" for simulation HeapsPeter Sanders' C++ implementation of heaps, with benchmark The Stony Brook Algorithm RepositoryStatement of priority queue problem and links to implementations Sorting and Searching ExperimentariumC and C++ programs for sorting, including bottom-up heapsort C++ BoostC++ implementation of d-heaps, Fibonacci heaps, pairing heaps, and splay heaps SWANSimulator Without A Name, with a C++ implementation of calendar queues Weak-HeapsortWeak-Heapsort, by Stefan Edelkamp Priority Queues and the STLHeaps, and an application to Huffman coding, by Mark Nelson Fifth DIMACS Challenge -- Priority Queue TestsPriority queue tests, with some pointers to implementations MLIB (DS) Commercial thread-safe software for data structures, in C and C++ Heap Implementations and VariationsDiscussion of several implementations using C++ testing tool Heaplab, by Jesper Bojesen D.D. Sleator's Splay TreesTop-down splay tree implementations and technical reports The AVL PageThreaded AVL tree library, and pointers to other AVL tree resources, by Ben Pfaff Mark Allen Weiss' Data Structures in Ada PagePriority queues in Ada Scheme implementation using pairing heapsby Darius Bacon TreapsScheme priority queue code, and some Usenet articles on priority queues, byOleg Kiselyov PriorityQueue.mMathematica package for destructive priority queues based on a heap libwayneWayne's Little Data Structures and Algorithms Library (in C) EZDSLEasy Data Structures Library for Delphi, by Julian Bucknall Bob++A library for sequential and parallel search algorithms Priority Queues and the van Emde Boas ImplementationIntroduction to the van Emde Boas implementation, by Mike WozniewskiRelated TopicsOne good way to find related pages, is to find ones that refer to this one.Here are some which deserve to be listed separately:NavigationA* search, intelligent path-finding, etc. Amit's A* PagesAmit's Thoughts on Path-Finding (and finding the right priority queue) data@{Codepage}Links to specialized pages like this one Collision Simulation For over a decade, a hobby of mine was to find the most efficient method tosimulate colliding balls. It started as a toy. Here is the latest version ofmy work:pool.zip (32-bit x86 program)It's a very old program, and it has a poor user-interface, but it's a goodillustration of a technique better than O(n2) per step for simulating n bouncing balls.Related links:Molecular Dynamics and Kinetic Theory Group Interactive and Exact Collision Detection for Virtual and Simulated Environments Impulse based simulation Discrete Event Systems Simulation Pending Event Set (PES) Structures for Discrete Event Simulations Ming C. LinHeap StatisticsAs an illustration of heaps, here are the most often visted links on thispage, arranged by type:Technical Reports* (including theses)152140351037734713228017532625012869957327014613515224474188561164246904750589196743670767134661505762491114936164016371526444718442631355147702941Software373710208975885528074635514952232693475182011842021361084431292111857815105369851521180119799Personal Home Pages2256220131393322122013142211311512111478131061385224645693107105552596553310674421221134Other Web Pages615851563122353577830321331707521251792342185687791146144048452341286122207015419435856151513633442292714331972417211111* Technical reports are usually binary files, and some are only available by subscription. Priority Queues SurveyIs closed.See results of the surveyAbout This PageThis page is a reference on Priority Queues, by Lee Killough.It was started in 1996 when I could find no real good online references onpriority queues.My introduction to priority queues was informal and spontaneous -- as a highschool student in the 1980s, playing at home on my then-ultra-slow computer(2 MHz), I wanted to find a fast way to simulate bouncingballs. It wasn't until years later, that I realized that what I had beenusing in my program, already had a name for it: Priority Queue.Priority queues are interesting, because:Priority queues come in more varieties and styles than most other data structures;The Heap Propertyis weak, yet strong enough for a priority queue's characteristics;Priority queues are dynamically changing, and so there's aneternal quality to them :-)Most of the referenced papers are available online, by following their titlelinks.A page with help on viewing files.Links to abstracts are usually provided, if they can be found in HTML orplaintext form.Unless a priority queue researcher has a home page, or a report that isavailable online, they are not usually listed. For references to offlinereports, see theHeap Bibliography.This page assumes that the reader has some knowledge of algorithms and datastructures. Those without any experience at all, are encouraged to visit theintroductory section.This page is one of the growing number of Theory Repositories On the Web,pages which single-mindedly explore a particular subject.For information on Queueing Theory, which is the study of waitinglines, and which is more about processes and phenomena than about datastructures, seeMyron Hlynka's Queueing Theory Page.For information about dynamic memory allocation (whose storage area is oftenmisleadingly called a "heap"), see Benjamin Zorn's Dynamic Storage Allocation and Memory Management Information Repository.Reports with more than one author are usually listed under the author who hasa home page, or the author with the most publications relating to priorityqueues. Although links to each report could be listed under every coauthor,they aren't, since this would involve a lot of unnecessary duplication. Items with * after them are usually only availableto subscribers of the publication they are published in.To find new reports on priority queues, I recommend doing a search onCiteSeer,or one ofthe search engines listed in this directory.(FermiVista! andCora used tobe my favorites, but they seem to have disappeared.)For researchers' homepages, see HPSearch.Why are external links put through a CGI redirection program? Because itallows the collection of statistics on which links are actually visited. It isintended to improve this page, by finding out which links are important andproviding them in an illustrative way, not to spy onvisitors. (In fact, this page goes out of its way to alert potential victimsof Spyware, by detectingit based on browser type, and redirecting the user to information about it.)I'm sorry, but I don't have the time to update this page much anymore.Pages which refer to this oneSelect a search engine:GoogleAltaVistaGlossary DecreaseKey (IncreaseKey) Increase the priority of an arbitrary pointed-to item, by decreasing (increasing) the value of its key. Delete Delete an arbitrary pointed-to item from the priority queue. DeleteMin (DeleteMax) Find and remove the minimum (or maxmium) keyed item in the priority queue. FindMin (FindMax) Find, but do not remove, the minimum (or maximum) keyed item in the priority queue. Heap A tree data structure in which every node's key is no larger (or no smaller) than its children's. The root node is a node with the smallest (or largest) key. Heapify Transform an arbitrary array of items into a heap. Usually more efficient than simply inserting items one at a time, hence the separate category. Insert Add an item to the priority queue. Meld Join two priority queues into a larger one. Often the basis for Insert. Priority Queue An abstract data type which efficiently keeps track of the item with the highest priority across a series of operations. The basic operations are: Insert, FindMin (or FindMax), and DeleteMin (or DeleteMax). Some implementations also efficiently support joining two priority queues (Meld), deleting an arbitrary item (Delete), and increasing the priority of an item (DecreaseKey or IncreaseKey). © 2003Lee Killough |
|
