We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item, and the set of k smallest items, from a heap-ordered tree, from a collection of sorted lists, and from X+Y, where X and Y are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the k-th smallest item, or the set of k smallest items, from a collection of m sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only O(m + sum_{i=1}^m log(k_i+1)) comparisons, where k_i is the number of items of the i-th list that belong to the overall set of k smallest items.
展开▼
机译：我们使用软堆来获得更简单的最优算法，用于从堆排序树，排序列表集合以及X + Y（其中X和Y）中选择第k个最小项和k个最小项的集合。是两个未排序的集合。我们的结果与Frederickson（1993）和Frederickson and Johnson（1982）的经典结果相匹配，并且在某种程度上得到了扩展和改进。特别地，为了从m个排序列表的集合中选择第k个最小项或k个最小项的集合，我们获得了一种新的最佳“输出敏感”算法，该算法仅执行O（m + sum_ {i = 1 } ^ m log（k_i + 1））比较，其中k_i是第i个列表的项目数量，该列表属于k个最小项目的整体集合。
展开▼
