Repeated random insertion into a priority queue

DOI10.1016/0196-6774(85)90028-8zbMATH Open0592.68022OpenAlexW1978276814MaRDI QIDQ3721798FDOQ3721798

Authors: Béla Bollobás, Istvan Simon 

Publication date: 1985

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(85)90028-8

Recommendations

• Analysis of insertion costs in priority trees
• Heaps on Heaps
• Average case analysis of heap building by repeated insertion
• Optimal algorithms for inserting a random element into a random heap
• Distribution-sensitive binomial queues.

zbMATH Keywords

insertionheappriority queuedata typelinearly ordered set

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms in computer science (68W99)

Cited In (9)

• Divisor generating functions and insertion into a heap
• A path integral approach to data structure evolution
• On the random construction of heaps
• Average case analysis of heap building by repeated insertion
• Recurrence relations on heaps
• The power of choice in priority scheduling
• Heap construction: Optimal in both worst and average cases?
• Analysis of insertion costs in priority trees
• A survey on priority queues

This page was built for publication: Repeated random insertion into a priority queue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3721798)