Refined complexity analysis for heap operations
A heap (priority queue) is a data structure for representing a set of items, each item having an associated numerical value, which facilitates such operations as insertion, deletion, merge (union), and findmin (find the item having the minimum value). It is well known that when n items are present the inherent complexity of these operations (in terms of comparisons) is log n per operation in the worst case. However, Cheriton and Tarjan have observed that when the frequency of findmin operations is small relative to the frequency of other operations, then certain implementations of heaps perform better than log n per operation. We explore this phenomenon with respect to inherent complexity.
- The amortized complexity of Henriksen's algorithm
- Stacks, queues, and deques with order-statistic operations
- Available stabilizing heaps
- Recurrence relations on heaps
- Optimizing binary heaps
- In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
- Heaps on Heaps
- scientific article; zbMATH DE number 1953023 (Why is no real title available?)
- scientific article; zbMATH DE number 1543353 (Why is no real title available?)
- Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers
- On computing an optimal permutation of ranks for multiselection
This page was built for publication: Refined complexity analysis for heap operations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578912)
