Median of heaps: linear-time selection by recursively constructing binary heaps

2023/04/24 by Oliver Serang, Serang, Oliver
Computer Science · #Advanced Malware Detection Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Software Testing and Debugging Techniques

paper · pdf · doi:10.48550/arxiv.2304.12313

openalex publication_date 2023/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The first worst-case linear-time algorithm for selection was discovered in 1973; however, linear-time binary heap construction was first published in 1964. Here we describe another worst-case linear selection algorithm,which is simply implemented and uses binary heap construction as its principal engine. The algorithm is implemented in place, and shown to perform similarly to in-place median of medians.

Related

• A Functional Approach to Standard Binary Heaps
• Dualheap Selection Algorithm: Efficient, Inherently Parallel and Somewhat Mysterious
• Selectable Heaps and Optimal Lazy Search Trees
• Selection on X₁ + X₁ + ⋯ X_m via Cartesian product tree
• Selection from heaps, row-sorted matrices and X+Y using soft heaps