A Dualheap Selection Algorithm - A Call for Analysis
| dc.creator | Sepesi, Greg | |
| dc.date | 2001-03-28 | |
| dc.date.accessioned | 2026-07-07T03:17:02Z | |
| dc.date.available | 2026-07-07T03:17:02Z | |
| dc.description | An algorithm is presented that efficiently solves the selection problem: finding the k-th smallest member of a set. Relevant to a divide-and-conquer strategy, the algorithm also partitions a set into small and large valued subsets. Applied recursively, this partitioning results in a sorted set. The algorithm's applicability is therefore much broader than just the selection problem. The presented algorithm is based upon R.W. Floyd's 1964 algorithm that constructs a heap from the bottom-up. Empirically, the presented algorithm's performance appears competitive with the popular quickselect algorithm, a variant of C.A.R. Hoare's 1962 quicksort algorithm. Furthermore, constructing a heap from the bottom-up is an inherently parallel process (processors can work independently and simultaneously on subheap construction), suggesting a performance advantage with parallel implementations. Given the presented algorithm's broad applicability, simplicity, serial performance, and parallel nature, further study is warranted. Specifically, worst-case analysis is an important but still unsolved problem. | |
| dc.description | 6 pages, 13 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0103023 | |
| dc.identifier | http://arxiv.org/abs/cs/0103023 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30576 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | F.2.2; E.1 | |
| dc.title | A Dualheap Selection Algorithm - A Call for Analysis | |
| dc.type | text |