Deterministic Cache-Oblivious Funnelselect
- Resource Type
- Working Paper
- Authors
- Brodal, Gerth Stølting; Wild, Sebastian
- Source
- Subject
- Computer Science - Data Structures and Algorithms
- Language
In the multiple-selection problem one is given an unsorted array $S$ of $N$ elements and an array of $q$ query ranks $r_1<\cdots0$, and $\Delta_i = r_{i} - r_{i-1}$ (assuming $r_0=0$ and $r_{q+1}=N + 1$).