Repeated random insertion into a priority queue

DOI10.1016/0196-6774(85)90028-8MaRDI QIDQ3721798zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

data typeheapinsertionlinearly ordered setpriority queue

Mathematics Subject Classification ID

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

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.

Cited in

(10)

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

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)