# Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps

**Authors:** Haim Kaplan, László Kozma, Or Zamir, Uri Zwick  
**arXiv:** [1802.07041](https://arxiv.org/abs/1802.07041)  
**Date:** 2018-02-20  
**Summary page:** https://www.summarizepaper.com/en/paper/1802.07041v1/

## Key points

- Soft heaps introduced as a concept
- Optimal algorithms for selecting the k-th smallest item and set of k smallest items from various data structures
- Results extend and improve upon classical results by Frederickson (1993) and Frederickson and Johnson (1982)
- Focus on efficient algorithms for selection from heap-ordered trees, collections of sorted lists, and sum of two unsorted sets
- Soft heaps simplify selection processes
- New optimal "output-sensitive" algorithm for selecting k-th smallest item or set of k smallest items from a collection of m sorted lists
- Algorithm performs O(m+∑(i=1)^m log(k_i+1)) comparisons, where k_i represents number of items in i-th list belonging to overall set of k smallest items
- Research provides insights into efficient selection algorithms using soft heaps
- Results match existing classical results while offering improvements in simplicity and optimality.

## Summary

The paper titled "Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps" by Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick introduces the concept of soft heaps and presents optimal algorithms for selecting the $k$-th smallest item and the set of $k$ smallest items from various data structures. The authors demonstrate that their results not only match but also extend and improve upon classical results by Frederickson (1993) and Frederickson and Johnson (1982). The main focus of this work is on developing efficient algorithms for selecting the $k$-th smallest item or the set of $k$ smallest items from different types of data structures. Specifically, the authors consider heap-ordered trees, collections of sorted lists, and the sum of two unsorted sets ($X+Y$). By utilizing soft heaps, they are able to simplify these selection processes. One notable contribution of this paper is a new optimal "output-sensitive" algorithm for selecting the $k$-th smallest item or the set of $k$ smallest items from a collection of $m$ sorted lists. This algorithm performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where $k_i$ represents the number of items in the $i$-th list that belong to the overall set of $k$ smallest items. Overall, this research provides valuable insights into efficient selection algorithms by leveraging soft heaps. The presented results not only match existing classical results but also offer improvements in terms of simplicity and optimality.