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

arXiv:1802.07041v1 [] 20 Feb 2018

Haim Kaplan

∗

László Kozma

†

Or Zamir

‡

Uri Zwick

§

Abstract
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 P
m sorted lists we obtain a new optimal “output-sensitive” algorithm that performs
m
only O(m + i=1 log(ki + 1)) comparisons, where ki is the number of items of the i-th list that
belong to the overall set of k smallest items.

1

Introduction

The input to the standard selection problem is a set of n items, drawn from a totally ordered
domain, and an integer 1 ≤ k ≤ n. The goal is to return the k-th smallest item in the set. A
classical result of Blum et al. [1] says that the selection problem can be solved deterministically in
O(n) time, i.e., faster than sorting the set. The number of comparisons required for selection was
reduced by Schönhage et al. [26] to 3n, and by Dor and Zwick [8, 9] to about 2.95n.
In the generalized selection problem, we are also given a partial order P known to hold for the set
of n input items. The goal is again to return the k-th smallest item. The corresponding generalized
sorting problem was extensively studied. It was shown by Kahn and Saks [20] that the problem
can be solved using only O(log e(P )) comparisons, where e(P ) is the number of linear extensions
of P . Thus, the information-theoretic lower bound is tight for generalized sorting. The algorithm
of Kahn and Saks [20] performs only O(log e(P )) comparisons, but may spend much more time on
deciding which comparisons to perform. Kahn and Kim [19] and Cardinal et al. [4] gave algorithms
that perform only O(log e(P )) comparisons and run in polynomial time.
A moment’s reflection shows that an algorithm that finds the k-th smallest item of a set, must also
identify the set of k smallest items of the set.1 Given a partial order P , let sk (P ) be the number of
∗

Blavatnik School of Computer Science, Tel Aviv University, Israel. Research supported by the Israel Science Foundation grant no. 1841-14 and by a grant from the Blavatnik Computer Science Fund. E-mail: haimk@post.tau.ac.il.
†
Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands.
E-mail:
Lkozma@gmail.com.
‡
Blavatnik School of Computer Science, Tel Aviv University, Israel. E-mail: orzamir@mail.tau.ac.il.
§
Blavatnik School of Computer Science, Tel Aviv University, Israel. E-mail: zwick@tau.ac.il.
1
The information gathered by a comparison-based algorithm corresponds to a partial order which can be represented by a DAG (Directed Acyclic Graph). Every topological sort of the DAG corresponds to a total order of the
items consistent with the partial order. Suppose that e is claimed to be the k-th smallest item and suppose, for
the sake of contradiction, that the set I of the items that are incomparable with e is non-empty. Then, there is a
topological sort in which e is before all the items of I, and another topological sort in which e is after all the items
of I, contradicting the fact that e is the k-th smallest item in all total orders consistent with the partial order.

1

subsets of size k that may possibly be the set of k smallest items in P . Then, log2 sk (P ) is clearly
a lower bound on the number of comparisons required to select the k-th smallest item, or the set
of k smallest items. Unlike sorting, this information-theoretic lower bound for selection may be
extremely weak. For example, the information-theoretic lower bound for selecting the minimum
is only log2 n, while n − 1 comparisons are clearly needed (and are sufficient). To date, there is
no characterization of pairs (P, k) for which the information-theoretic lower bound for selection is
tight, nor an alternative general technique to obtain a tight lower bound.
Frederickson and Johnson [12, 13, 14] and Frederickson [11] studied the generalized selection problem for some interesting specific partial orders. Frederickson [11] considered the case in which the
input items are items of a binary min-heap, i.e., they are arranged in a binary tree, with each item
smaller than its two children. Frederickson [11] gave a complicated algorithm that finds the k-th
smallest item using only O(k) comparisons, matching the information-theoretic lower bound for
this case. (Each subtree of size k of the heap, containing the root, can correspond to the set of k
1 2k
smallest items, and there are k+1
k , the k-th Catalan number, such subtrees.)
Frederickson and Johnson [12, 13, 14] considered three other interesting special cases. (i) The input
items are in a collection of sorted lists, or equivalently they reside in a row-sorted matrix; (ii) The
input items reside in a collection of matrices, where each matrix is both row- and column-sorted;
(iii) The input items are X + Y , where X and Y are unsorted sets of items.2 For each of these
cases, they present a selection algorithm that matches the information-theoretic lower bound.
We note in passing that sorting X + Y is a well studied problem. Fredman [15] showed that
X + Y , where |X| = |Y | = n, can be sorted using only O(n2 ) comparisons, but it is not known
how to do it in O(n2 ) time. (An intriguing situation!) Fredman [15] also showed that Ω(n2 )
comparisons are required, if only comparisons between items in X + Y , i.e., comparisons of the
form xi + yj ≤ xk + y` , are allowed. Lambert [24] and Steiger and Streinu [27] gave algorithms that
sort X + Y in O(n2 log n) time using only O(n2 ) comparisons. Kane et al. [21], in a breakthrough
result, have shown recently that X + Y can be sorted using only O(n log2 n) comparisons of the
form (xi + yj ) − (xi0 + yj 0 ) ≤ (xk + y` ) − (xk0 + y`0 ), but it is again not known how to implement
their algorithm efficiently.
The median of X + Y , on the other hand, can be found in O(n log n) time, and O(n log n) comparisons of items in X + Y , as was already shown by Johnson and Mizoguchi [18] and Johnson and
Kashdan [17]. The selection problem from X + Y becomes more challenging when k = o(n2 ).
Frederickson [11] gives two applications for selection from a binary min-heap. The first is in
an algorithm for listing the k smallest spanning trees of an input graph. The second is a certain
resource allocation problem. Eppstein [10] uses the heap selection algorithm in his O(m+n log n+k)
algorithm for generating the k shortest paths between a pair of vertices in a digraph. As pointed
out by Frederickson and Johnson [13], selection from X + Y can be used to compute the HodgesLehmann [16] estimator in statistics. Selection from a matrix with sorted rows solves the problem
of
“optimum discrete distribution
of effort” with concave functions, i.e., the problem of maximizing
Pm
Pm
f
(k
)
subject
to
k
=
k,
where the fi ’s are concave and the ki ’s are non-negative integers.
i=1 i i
i=1 i
(See Koopman [23] and other references in [13].) Selection from a matrix with sorted rows is also
used by Brodal et al. [3] and Bremner et al. [2].
The O(k) heap selection algorithm of Frederickson [11] is fairly complicated. The naı̈ve algorithm
for the problem runs in O(k log k) time. Frederickson first improves this to O(k log log k), then to
∗
∗
O(k3log k ), then to O(k2log k ), and finally to O(k).
Our first result is a very simple O(k) heap selection algorithm obtained by running the naı̈ve
O(k log k) algorithm using an auxiliary soft heap instead of a standard heap. Soft heaps, discussed
2

By X + Y we mean the set of pairwise sums {x + y | x ∈ X, y ∈ Y }.

2

below, are fairly simple data structures whose implementation is not much more complicated than
the implementation of standard heaps. Our overall O(k) algorithm is thus simple and easy to
implement and comprehend.
Relying on our simple O(k) heap selection algorithm, we obtain simplified algorithms for selection
from row-sorted matrices and from X +Y . Selecting the k-th item from a row-sorted matrix with m
k
rows using our algorithms requires O(m + k) time, if k ≤ 2m, and O(m log m
) time, if k ≥ 2m,
matching the optimal results of Frederickson and Johnson [12]. Furthermore,
we obtain a new
P
optimal “output-sensitive” algorithm whose running time is O(m + m
log(k
+
1)), where ki is
i
i=1
the number of items of the i-th row that belong to the set of k smallest items in the matrix. We
also use our simple O(k) heap selection algorithm to obtain simple optimal algorithms for selection
from X + Y .
Soft heaps are “approximate” priority queues introduced by Chazelle [6]. They form a major
building block in his deterministic O(mα(m, n))-time algorithm for finding minimum spanning trees
[5], which is currently the fastest known deterministic algorithm for the problem. Chazelle [6] also
shows that soft heaps can be used to obtain a simple linear time (standard) selection algorithm. (See
the next section.) Pettie and Ramachandran [25] use soft heaps to obtain an optimal deterministic
minimum spanning algorithm with a yet unknown running time. A simplified implementation of
soft heaps is given in Kaplan et al. [22].
All algorithms considered in the paper are comparison-based, i.e., the only operations they perform
on the input items are pairwise comparisons. In the selection from X + Y problem, the algorithms
make pairwise comparisons in X, in Y and in X + Y . The number of comparisons performed by
the algorithms presented in this paper dominates the total running time of the algorithms.
The rest of the paper is organized as follows. In Section 2 we review the definition of soft heaps. In
Section 3 we describe our heap selection algorithms. In Section 3.1 we describe our basic algorithm
for selection from binary min-heaps. In Sections 3.2 and 3.3 we extend the algorithm to d-ary
heaps and then to general heap-ordered trees and forests. In Section 4 we describe our selection
algorithms from row-sorted matrices. In Section 4.1 we describe a simple O(m + k) algorithm
which is optimal if k = O(m). In Section 4.2 we build on the O(m + k) algorithm to obtain an
k
optimal O(m log m
) algorithm, for k ≥ 2m. In Sections 4.3 and 4.4 we obtain new results
that were
Pm
not obtained by Frederickson and Johnson [12]. In Section 4.3 we obtain an O(m + i=1 log ni )
algorithm, wherePni ≥ 1 is the length of the i-th row of the matrix. In Section 4.4 we obtain
the new O(m + m
i=1 log(ki + 1)) optimal output-sensitive algorithm. In Section 5 we present our
selection algorithms from X + Y . In Section 5.1 we give a simple O(m + n + k) algorithm, where
k
|X| = m, |Y | = n. In Section 5.2 we give a simple O(m log m
) algorithm, for m ≥ n and k ≥ 6m.
We conclude in Section 6 with some remarks and open problems.

2

Soft heaps

Soft heaps, invented by Chazelle [6], support the following operations:
soft-heap(ε): Create and return a new, empty soft heap with error parameter ε.
insert(Q, e): Insert item e into soft heap Q.
meld(Q1 , Q2 ): Return a soft heap containing all items in heaps Q1 and Q2 , destroying Q1 and Q2 .
extract-min(Q): Delete from the soft heap and return an item of minimum key in heap Q.
In Chazelle [6], extract-min operations are broken into find-min and delete operations. We only
need combined extract-min operations. We also do not need meld operations in this paper.

3

The main difference between soft heaps and regular heaps is that soft heaps are allowed to increase
the keys of some of the items in the heap by an arbitrary amount. Such items are said to become
corrupt. The soft heap implementation chooses which items to corrupt, and by how much to
increase their keys. The only constraint is that for a certain error parameter 0 ≤ ε < 1, the
number of corrupt items in the heap is at most εI, where I is the number of insertions performed
so far. The ability to corrupt items allows the implementation of soft heaps to use what Chazelle [6]
calls the “data structures equivalent of car pooling” to reduce the amortized time per operation
to O(log 1ε ), which is the optimal possible dependency on ε. In the implementation of Kaplan et
al. [22], extract-min operations take O(log 1ε ) amortized time, while all other operations take O(1)
amortized time. (In the implementation of Chazelle [6], insert operations take O(log 1ε ) amortized
time while the other operations take O(1) time.)
An extract-min operation returns an item whose current, possibly corrupt, key is the smallest in
the heap. Ties are broken arbitrarily. (Soft heaps usually give many items the same corrupt key,
even if initially all keys are distinct.) Each item e thus has two keys associated with it: its original
key e.key, and its current key in the soft heap e.key 0 , where e.key ≤ e.key 0 . If e.key < e.key 0 ,
then e is corrupt. The current key of an item may increase several times.
At first sight, it may seem that the guarantees provided by soft heaps are extremely weak. The only
bound available is on the number of corrupt items currently in the heap. In particular, all items
extracted from the heap may be corrupt. Nonetheless, soft heaps prove to be an extremely useful
data structure. In particular, they play a key role in the fastest known deterministic algorithm of
Chazelle [5] for finding minimum spanning trees.
Soft heaps can also be used, as shown by Chazelle [6], to select an approximate median of n items.
Initialize a soft heap with some error parameter ε < 21 . Insert the n items into the soft heap and
then perform (1 − ε) n2 extract-min operations. Find the maximum item e, with respect to the
original keys, among the extracted items. The rank of e is between (1 − ε) n2 and (1 + ε) n2 . The
rank is at least (1 − ε) n2 as e is the largest among (1 − ε) n2 items. The rank is at most (1 + ε) n2 as
the items remaining in the soft heap that are smaller than e must be corrupt, so there are at most
εn such items. For, say, ε = 41 , the running time of the algorithm is O(n).
Using a linear time approximate median algorithm, we can easily obtain a linear time algorithm for
selecting the k-th smallest item. We first compute the true rank r of the approximate median e.
If r = k we are done. If r > k, we throw away all items larger than e. Otherwise, we throw away
all items smaller than e and replace k by k − r. We then continue recursively. In O(n) time, we
reduced n to at most ( 12 + ε)n, so the total running time is O(n).
In this paper, we show the usefulness of soft heaps in solving generalized selection problems. We
obtain simpler algorithms than those known before, and some results that were not known before.
In Chazelle [6] and Kaplan et al. [22], soft heaps may corrupt items while performing any type of
operation. It is easy, however, to slightly change the implementation of [22] such that corruptions
only occur following extract-min operations. In particular, insert operations do not cause corruption, and an extract-min operation returns an item with a smallest current key at the beginning
of the operation. These assumptions simplify algorithms that use soft heaps, and further simplify
their analysis. The changes needed in the implementation of soft heaps to meet these assumptions
are minimal. The operations insert (and meld) are simply implemented in a lazy way. The implementation of [22] already has the property that extract-min operations cause corruptions only
after extracting an item with minimum current key.
We assume that an extract-min operation returns a pair (e, C), where e is the extracted item,
and C is a list of items that became corrupt after the extraction of e, i.e., items that were not
corrupt before the operation, but are corrupt after it. We also assume that e.corrupt is a bit that
says whether e is corrupt. (Note that e.corrupt is simply a shorthand for e.key < e.key 0 .) It is
4

Soft-Select(r):
S←∅
Q ← soft-heap(1/4)
insert(Q, r)
append(S, r)

Heap-Select(r):
S←∅
Q ← heap()
insert(Q, r)
for i ← 1 to k do
e ← extract-min(Q)
append(S, e)
insert(Q, e.left)
insert(Q, e.right)
return S

for i ← 1 to k − 1 do
(e, C) ← extract-min(Q)
if not e.corrupt then C ← C ∪ {e}
for e ∈ C do
insert(Q, e.left)
insert(Q, e.right)
append(S, e.left)
append(S, e.right)

Figure 1: Extracting the k smallest
items from a binary min-heap with
root r using a standard heap.

return select(S, k)
Figure 2: Extracting the k smallest items from a
binary min-heap with root r using a soft heap.

again easy to change the implementation of [22] so that extract-min operations return a list C of
newly corrupt items, without affecting the amortized running times of the various operations. (In
particular, the amortized running time of an extract-min operation is still O(log 1ε ), independent
of the length of C. As each item becomes corrupt only once, it is easy to charge the cost of adding
an item to C to its insertion into the heap.)
We stress that the assumptions we make on soft heaps in this paper can be met by minor and
straightforward modifications of the implementation of Kaplan et al. [22], as sketched above. No
complexities are hidden here. We further believe that due to their usefulness, these assumptions
will become the standard assumptions regarding soft heaps.

3

Selection from heap-ordered trees

In Section 3.1 we present our simple, soft heap-based, O(k) algorithm for selecting the k-th smallest
item, and the set of k smallest items from a binary min-heap. This algorithm is the cornerstone
of this paper. For simplicity, we assume throughout this section that the input heap is infinite. In
particular, each item e in the input heap has two children e.left and e.right. (A non-existent child
is represented by a dummy item with key +∞.) In Section 3.2 we adapt the algorithm to work for
d-ary heaps, for d ≥ 3, using “on-the-fly ternarization via heapification”. In Section 3.3 we extend
the algorithm to work on any heap-ordered tree or forest. The results of Section 3.3 are new.

3.1

Selection from binary heaps

The naı̈ve algorithm for selection from a binary min-heap is given in Figure 1. The root r of the
input heap is inserted into an auxiliary heap (priority queue). The minimal item e is extracted
from the heap and appended to a list S. The two children of e, if they exist, are inserted into the
heap. This operation is repeated k times. After k iterations, the items in S are the k smallest items
in the input heap, in sorted order. Overall, 2k + 1 items are inserted into the heap and k items are

5

Figure 3: Types of items in the input heap. White nodes belong to A, i.e., were not inserted yet
into the soft heap Q; black nodes belong to the barrier B; gray nodes belong to C, i.e., are corrupt;
striped nodes belong to D, i.e., were already deleted.
extracted, so the total running time is O(k log k), which is optimal if the k smallest items are to be
reported in sorted order.
Frederickson [11] devised a very complicated algorithm that outputs the k smallest items, not
necessarily in sorted order, in only O(k) time, matching the information-theoretic lower bound. In
Figure 2 we give our very simple algorithm Soft-Select(r) for the same task, which also runs in
optimal O(k) time and performs only O(k) comparisons. Our algorithm is a simple modification
of the naı̈ve algorithm of Figure 1 with the auxiliary heap replaced by a soft heap. The resulting
algorithm is much simpler than the algorithm of Frederickson [11].
Algorithm Soft-Select(r) begins by initializing a soft heap Q with error parameter ε = 1/4 and by
inserting the root r of the input heap into it. Items inserted into the soft heap Q are also inserted
into a list S. The algorithm then performs k − 1 iterations. In each iteration, the operation
(e, C) ← extract-min extracts an item e with the smallest (possibly corrupt) key currently in Q,
and also returns the set of items C that become corrupt as a result of the removal of e from Q. If e
is not corrupt, then it is added to C. Now, for each item e ∈ C, we insert its two children e.left
and e.right into the soft heap Q and the list S.
Lemma 3.1 below claims that Soft-Select(r) inserts the k smallest items of the input heap into
the soft heap Q. Lemma 3.2 claims that, overall, only O(k) items are inserted into Q, and hence
into S. Thus, the k smallest items in the input heap can be found by selecting the k smallest items
in the list S using a standard selection algorithm.
Lemma 3.1 Algorithm Soft-Select(r) inserts the k smallest items from the input binary minheap into the soft heap Q. (Some of them may subsequently be extracted from the heap.)
Proof: At the beginning of an iteration of algorithm Soft-Select, let A be the set of items of the
input binary heap that were not yet inserted into the soft heap Q; let B be the set of items that
were inserted, not yet removed and are not corrupt; let C be the set of items that were inserted,
not yet removed, and are corrupt; let D be the set of items that were inserted and already deleted
from Q. We prove below, by easy induction, the following two invariants:
(a) All strict ancestors of items in B are in C ∪ D.
(b) Each item in A has an ancestor in B.

6

Thus, the items in B form a barrier that separates the items of A, i.e., items that were not inserted
yet into the heap, from the items of C ∪ D, i.e., items that were inserted and are either corrupt or
were already removed from the soft heap Q. For an example, see Figure 3.
Invariants (a) and (b) clearly hold at the beginning of the first iteration, when B = {r} and the
other sets are empty. Assume that (a) and (b) hold at the beginning of some iteration. Each
iteration removes an item from the soft heap. The item removed is either a corrupt item from C, or
an item (in fact the smallest item) on the barrier B. Following the extraction, some items on the
barrier B become corrupt and move to C. The barrier is ‘mended’ by inserting to Q the children
of items on B that were extracted or became corrupt. By our simplifying assumption, insertions
do not corrupt items, so the newly inserted items belong to B and are thus part of the new barrier,
reestablishing (a) and (b).
We now make the following two additional claims:
(c) The item extracted at each iteration is smaller than or equal to the smallest item on the
barrier. (With respect to the original keys.)
(d) The smallest item on the barrier cannot decrease.
Claim (c) follows immediately from the definition of an extract-min operation and our assumption
that corruption occurs only after an extraction. All the items on the barrier, and in particular the
smallest item e on the barrier, are in the soft heap and are not corrupt. Thus, the extracted item
is either e, or a corrupt item f whose corrupt key is still smaller than e. As corruption can only
increase keys, we have f < e.
Claim (d) clearly holds as items on the barrier at the end of an iteration were either on the barrier
at the beginning of the iteration, or are children of items that were on the barrier at the beginning
of the iteration.
Consider now the smallest item e on the barrier after k − 1 iterations. As all extracted items are
smaller than it, the rank of e is at least k. Furthermore, all items smaller than e must be in C ∪ D,
i.e., inserted at some stage into the heap. Indeed, let f be an item of A, i.e., an item not inserted
into Q. By invariant (b), f has an ancestor f 0 on the barrier. By heap order and the assumption
that e is the smallest item on the barrier we indeed get e ≤ f 0 < f . Thus, the smallest k items
were indeed inserted into the soft heap as claimed.
2
The proof of Lemma 3.1 relies on our assumption that corruptions in the soft heap occur only
after extract-min operations. A slight change in the algorithm is needed if insert operations may
cause corruptions; we need to repeatedly add children of newly corrupt items until no new items
become corrupt. (Lemma 3.2 below shows that this process must end if ε < 21 . The process may not
end if ε ≥ 21 .) The algorithm, without any change, remains correct, and in particular Lemma 3.1
holds, if extract-min operations are allowed to corrupt items before extracting an item of minimum
(corrupt) key. The proof, however, becomes more complicated. (Claim (c), for example, does not
hold in that case.)
Lemma 3.2 Algorithm Soft-Select(r) inserts only O(k) items into the soft heap Q.
Proof: Let I be the number of insertions made by Soft-Select(r), and let C be the number of
items that become corrupt during the running of the algorithm. (Note that Soft-Select(r) clearly
terminates.) Let ε(= 41 ) be the error parameter of the soft heap. We have I < 2k + 2C, as each
inserted item is either the root r, or a child of an item extracted during one of the k − 1 iterations
of the algorithm, and there are at most 2k − 1 such insertions, or a child of a corrupt item, and
there are exactly 2C such insertions. We also have C < k + εI, as by the definition of soft heaps,
7

at the end of the process at most εI items in the soft heap may be corrupt, and as only k − 1
(possibly corrupt) items were removed from the soft heap. Combining these two inequalities we get
C < k + ε(2k + 2C), and hence (1 − 2ε)C < (1 + 2ε)k. Thus, if ε < 12 we get


1 + 2ε
1 + 2ε
k.
C <
k , I < 2 1+
1 − 2ε
1 − 2ε
The number of insertions I is therefore O(k), as claimed. (For ε = 41 , I < 8k.)

2

Combining the two lemmas we easily get:
Theorem 3.3 Algorithm Soft-Select(r) selects the k smallest items of a binary min-heap in O(k)
time.
Proof: The correctness of the algorithm follows from Lemmas 3.1 and 3.2. Lemma 3.2 also implies
that only O(k) operations are performed on the soft heap. As ε = 1/4, each operation takes O(1)
amortized time. The total running time, and the number of comparisons, performed by the loop of
Soft-Select(r) is thus O(k). As the size of S is O(k), the selection of the smallest k items from S
also takes only O(k) time.
2

3.2

Selection from d-ary heaps

Frederickson [11] claims, in the last sentence of his paper, that his algorithm for binary min-heaps
can be modified to yield an optimal O(dk) algorithm for d-ary min-heaps, for any d ≥ 2, but no
details are given. (In a d-ary heap, each node has (at most) d children.)
We present two simple O(dk) algorithms for selecting the k smallest items from a d-ary min-heap.
The first is a simple modification of the algorithm for the binary case. The second in a simple
reduction from the d-ary case to the binary case.
Algorithm Soft-Select(r) of Figure 2 can be easily adapted to work on d-ary heaps. We simply
insert the d children of an extracted item, or an item that becomes corrupt, into the soft heap. If
we again let I be the number of items inserted into the sort heap, and C be the number of items
that become corrupt, we get I < d(k + C) and C < k + εI, and hence


1 + dε
1 + dε
C <
k , I < d 1+
k,
1 − dε
1 − dε
1
provided that ε < d1 , e.g., ε = 2d
. The algorithm then performs O(dk) insert operations, each
with an amortized cost of O(1), and k − 1 extract-min operations, each with an amortized cost of
O(log 1ε ) = O(log d). The total running time is therefore O(dk). (Note that it is important here to
use the soft heap implementation of [22], with an O(1) amortized cost of insert.)

An alternative O(dk) algorithm for d-ary heaps, for any d ≥ 2, can be obtained by a simple reduction
from d-ary heaps to 3-ary (or binary) heaps using a process that we call “on-the-fly ternarization
via heapification”. We use the well-known fact that an array of d items can be heapified, i.e.,
converted into a binary heap, in O(d) time. (See Williams [28] or Cormen et al. [7].) We describe
this alternative approach because we think it is interesting, and because we use it in the next section
to obtain an algorithm for general heap-ordered trees, i.e., trees in which different nodes may have
different degrees, and the degrees of the nodes are not necessarily bounded by a constant.
In a d-ary heap, each item e has (up to) d children e.child[1], . . . , e.child[d]. We construct a ternary
heap on the same set of items in the following way. We heapify the d children of e, i.e., construct
8

Figure 4: On-the-fly ternarization of a 7-ary heap. Thin lines represent the original 7-ary heap.
Bold arrows represent new left and right children. Dashed arrows represent new middle children.
a binary heap whose items are these d children. This gives each child f of e two new children
f.left and f.right. (Some of these new children are null.) We let e.middle be the root of the heap
composed of the children of e. Overall, this gives each item e in the original heap three new children
e.left, e.middle and e.right, some of which may be null. Note that e gets its new children e.left
and e.right when it and its siblings are heapified. (The names left, middle and right are, of course,
arbitrary.) For an example, see Figure 4.
This heapification process can be carried out on-the-fly while running Soft-Select(r) on the resulting ternary heap. The algorithm starts by inserting the root of the d-ary heap, which is also the
root of its ternarized version, into the soft heap. When an item e is extracted from the soft heap, or
becomes corrupt, we do not immediately insert its d original children into the soft heap. Instead, we
heapify its d children, in O(d) time. This assigns e its middle child e.middle. Item e already has its
left and right children e.left and e.right defined. The three new children e.left, e.middle and e.right
are now inserted into the soft heap. We call the resulting algorithm Soft-Select-Heapify(r).
Theorem 3.4 Algorithm Soft-Select-Heapify(r) selects the k smallest items from a d-ary heap
with root r in O(dk) time.
Proof: Algorithm Soft-Select-Heapify(r) essentially works on a ternary version of the input
d-ary heap constructed on the fly. Simple adaptations of Lemmas 3.1 and 3.2 show that the total
running time, excluding the heapifications’ cost, is O(k). As only O(k) heapifications are performed,
the cost of all heapifications is O(dk), giving the total running time of the algorithm.
2
It is also possible to binarize the input heap on the fly. We first ternarize the heap as above.
We now convert the resulting ternary tree into a binary tree using the standard first child, next
sibling representation. This converts the ternary heap into a binary heap, if the three children
of each item are sorted. During the ternarization process, we can easily make sure that the three
children of each item appear in sorted order, swapping children if necessary, so we can apply this
final binarization step.

9

3.3

Selection from general heap-ordered trees

Algorithm Soft-Select-Heapify(r) works, of course, on arbitrary heap-ordered trees in which
different nodes have different degrees. Algorithm Soft-Select(r), on the other hand, is not easily
adapted to work on general heap-ordered trees, as it is unclear how to set the error parameter ε
to obtain an optimal running time. To bound the running time of Soft-Select-Heapify(r) on an
arbitrary heap-ordered tree, we introduce the following definition.
Definition 3.5 (D(T, k)) Let T be a (possibly infinite) rooted tree and let k ≥ 1. Let D(T, k) be
the maximum sum of degrees over all subtrees of T of size k rooted at the root of T . (The degrees
summed are in T , not in the subtree.)
For example, if Td is an infinite d-ary tree, then D(Td , k) = dk, as the sum of degrees in each
subtree of Td containing k vertices is dk. For a more complicated example, let T be the infinite
tree in which each node at level i has degree
P i + 2, i.e., the root has two children, each of which
has three children, etc. Then, D(T, k) = k+1
i=2 i = k(k + 3)/2, where the subtrees achieving this
maximum are paths starting at the root. A simple adaptation of Theorem 3.4 gives:
Theorem 3.6 Let T be a heap-ordered tree with root r. Algorithm Soft-Select-Heapify(r) selects
the k-th smallest item in T , and the set of k smallest items in T , in O(D(T, 3k)) time.
Proof: We use the on-the-fly binarization and a soft heap with ε = 61 . The number of corrupt
items is less than 2k. The number of extracted items is less than k. Thus, the algorithm needs to
heapify the children of less than 3k items that form a subtree T 0 of the original tree T . The sum
of the degrees of these items is at most D(T, 3k), thus the total time spent on the heapifications,
which dominates the running time of the algorithm, is O(D(T, 3k)). We note that D(T, 3k) can be
replaced by D(T, (2 + δ)k), for any δ > 0, by choosing ε small enough.
2
Theorem 3.7 Let T be a heap-ordered tree and let k ≥ 1. Any comparison-based algorithm for
selecting the k-th smallest item in T must perform at least D(T, k − 1) − (k − 1) comparisons on
some inputs.
Proof: Let T 0 be the subtree of T of size k − 1 that achieves the value D(T, k − 1), i.e., the sum of
the degrees of the nodes of T 0 is D(T, k − 1). Suppose the k − 1 items of T 0 are the k − 1 smallest
items in T . The nodes of T 0 have at least D(T, k − 1) − (k − 2) children that are not in T 0 . The
k-th smallest item is the minimum item among these items, and no information on the order of
these items is implied by the heap order of the tree. Thus, finding the k-th smallest item in this
case requires at least D(T, k − 1) − (k − 1) comparisons.
2

4

Selection from row-sorted matrices

In this section we present algorithms for selecting the k smallest items from a row-sorted matrix, or
equivalently from a collection of sorted lists. Our results simplify and extend results of Frederickson
and Johnson [12]. The algorithms presented in this section use our Soft-Select algorithm for
selection from a binary min-heap presented in Section 3.1. (Frederickson’s [11] algorithm could also
be used, but the resulting algorithms would become much more complicated, in particular more
complicated than the algorithms of Frederickson and Johnson [12].)

10

Figure 5: Partitioning the items in each row to blocks of size b. Block representatives are shown
as small filled circles. The shaded regions contains the k smallest items. The darkly shaded region
depicts blocks all of whose items are among the k smallest.
In Section 4.1 we give an O(m + k) algorithm, where m is the number of rows, which is optimal
if m = O(k). In Section 4.2 we give an O(m log k+m
m ) algorithm which is optimal for k = Ω(m).
These results match results given by Frederickson and Johnson [12]. In Sections 4.3 and 4.4 we
give two new algorithms that improve in some cases over the previous algorithms.

4.1

An O(m + k) algorithm

A sorted list may be viewed as a heap-sorted path, i.e., a 1-ary heap. We can convert a collection
of m sorted lists into a (degenerate) binary heap by building a binary tree whose leaves are the first
items in the lists. The values of the m − 1 internal nodes in this tree are set to −∞. Each item in
a list will have one real child, its successor in the list, and a dummy child with value +∞. To find
the k smallest items in the lists, we simply find the m+k −1 smallest items in the binary heap. This
can be done in O(m + k) time using algorithm Soft-Select of Section 3.1. More directly, we can
use the following straightforward modification of algorithm Soft-Select. Insert the m first items
in the lists into a soft heap. Perform k − 1 iterations in which an item with minimum (corrupt)
key is extracted. Insert into the soft heap the child of the item extracted as well as the children of
all the items that became corrupt following the extract-min operation.
Alternatively, we can convert the m sorted lists into a heap-ordered tree Tm,1 by adding a root
with value −∞ that will have the m first items as its children. All other nodes in the tree will have
degree 1. It is easy to see that D(Tm,1 , k) = m + k − 1. By Theorem 3.6 we again get an O(m + k)
algorithm. We have thus presented three different proofs of the following theorem.
Theorem 4.1 Let A be a row-sorted matrix containing m rows. Then, the k-th smallest item in A,
and the set of k smallest items in A, can be found in O(m + k) time.
We refer to the algorithm of Theorem 4.1 as Mat-Select1 (A, k). The O(m + k) running time of
Mat-Select1 (A, k) is asymptotically optimal if k = O(m), as Ω(m) is clearly a lower bound; each
selection algorithm must examine at least one item in each row of the input matrix.

4.2

k
An O(m log m
) algorithm, for k ≥ 2m

We begin with a verbal description of the algorithm. Let A be
 the input matrix and let k ≥ 2m.
k
Partition each row of the matrix A into blocks of size b = 2m
. The last item in each block is the
11

Mat-Select2 (A, k):
m ← num-rows(A)
if k ≤ 2m then
return Mat-Select1 (A, k)
else
b ← bk/(2m)c
A0 ← jump(A, b)
K ← Mat-Select1 (A0 , m)
A00 ← shift(A, bK)
return bK + Mat-Select2 (A00 , k − bm)
Figure 6: Selecting the k smallest items from a row-sorted matrix A. (Implicit handling of submatrices passed to recursive calls.)
Mat-Select2 (hA, c, Di, k):
m ← num-rows(A)
if k ≤ 2m then
return Mat-Select1 (hA, c, Di, k)
else
b ← bk/(2m)c
K ← Mat-Select1 (hA, bc, Di, m)
return bK + Mat-Select2 (hA, c, D + bcKi, k − bm)
Figure 7: Selecting the k smallest items from a row-sorted matrix A. (Explicit handling of submatrices passed to recursive calls.)

representative of the block. Consider the (yet unknown) distribution of the k smallest items among
the m rows of the matrix. Let ki be the number of items in the i-th row that are among the k
smallest items in the whole matrix. These ki items are clearly the first ki items of the i-th row.
They are partitioned into a number of full blocks, followed possibly by one partially filled block.
 k 
(For an example, see Figure 5.) The number of items in partially filled blocks is at most m 2m
.
Thus, the number of filled blocks is at least
 k 
k − m 2m
 k 
≥ m.
2m

Apply algorithm Mat-Select1 to select the smallest m block representatives. This clearly takes
only O(m) time. (Algorithm Mat-Select1 is applied on the implicitly represented matrix A0 of
block representatives.) All items in the m blocks whose representatives were
are among

 k selected
k
the k smallest items of the matrix. The number of such items is mb = m 2m ≥ 4 , as k ≥ 2m.
These items can be removed from the matrix. All that remains is to select the k − mb smallest
remaining items using a recursive call to the algorithm. In each recursive call (or iteration), the
total work is O(m). The number of items to be selected drops by a factor of at least 3/4. Thus
k
k
after at most log4/3 2m
= O(log m
) iterations, k drops below 2m and then Mat-Select1 is called to
finish the job in O(m) time.
Pseudo-code of the algorithm described above, which we call Mat-Select2 (A, k) is given in Figure 6.
The algorithm returns an array K = (k1 , k2 , . . . , km ), where ki is the number of items in the i-th
12

row that are among the k smallest items of the matrix. The algorithm uses a function num-rows(A)
that returns the number of rows of a given matrix, a function jump(A, b) that returns an (implicit)
representation of a matrix A0 such that A0i,j = Ai,bj , for i, j ≥ 1, and a function shift(A, K) that
returns an (implicit) representation of a matrix A00 such that A00i,j = Ai,j+ki , for i, j ≥ 1.
In Figure 7 we eliminate the use of jump and shift and make everything explicit. The input
matrix is now represented by a triplet hA, c, Di, where A is a matrix, c ≥ 1 is an integer, and
D = (d1 , d2 , . . . , dm ) is an array of non-negative integral displacements. Mat-Select2 (hA, c, Di, k)
selects the k smallest items in the matrix A0 such that A0i,j = Ai,cj+di , for i, j ≥ 1. To select the k
smallest items in A itself, we simply call Mat-Select2 (hA, 1, 0i, k), where 0 represents an array
of m zeros. The implementation of Mat-Select2 (hA, c, Di, k) in Figure 7 is recursive. It is easy to
convert it into an equivalent iterative implementation.
Theorem 4.2 Let A be a row-sorted matrix containing m rows and let k ≥ 2m. Algorithm
k
Mat-Select2 (A, k) selects the k smallest items in A in O(m log m
) time.
k
Frederickson and Johnson [12] showed that the O(m log m
) running time of Mat-Select2 (A, k) is
optimal, when k ≥ 2m. A simple proof of this claim can also be found in Section 4.5.

4.3

An O(m +

Pm

i=1

log ni ) algorithm

Assume now that the i-th row of A contains only ni items. We assume that ni ≥ 1, as otherwise,
we can simply remove the i-th row. We can run algorithms Mat-Select1 and Mat-Select2 of the
previous sections by adding dummy +∞ items at the end of each row, but this may be wasteful.
We now show that a simple modification
of Mat-Select2 , which we call Mat-Select3 , can solve
Pm
the selection problem in O(m + i=1 log ni ) time. We focus first on the number of comparisons
performed by the new algorithm.
 k 
At the beginning of each iteration, Mat-Select2 sets the block size to b = 2m
. PIf ni < b,
m
then the last item in the first block of the i-th row is +∞. Assuming that k ≤
i=1 ni , no
representatives from the i-th row will be selected in the current iteration. There is therefore no
point in considering the i-th row in the current iteration. Let m0 be the number of long rows, i.e.,
k
rows for which ni ≥ 2m
. We want to reduce the running time of the iteration to O(m0 ) and still
reduce k by some constant factor.
 k  k
The total number of items in the short rows is less than m 2m
≤ 2 . The long rows thus contain
k
at least 2 of the k smallest items of the matrix. We can thus run an iterationjof Mat-Select
2 on
k
 k 
k
k0
0
0
the long rows with k = 2 . In other words, we adjust the block size to b = 2m0 = 4m0 and
0

use Mat-Select1 to select the m0 smallest representatives. This identifies b0 m0 ≥ k4 ≥ k8 items as
belonging to the k smallest items in A. Thus, each iteration takes O(m0 ) time and reduces k by a
factor of at least 87 .
In how many iterations did each row of the matrix participate?
j k Let kj be the number of items still
kj
be the threshold for long rows used
to be selected at the beginning of iteration j. Let bj = 2m
in iteration j. As kj drops exponentially, so does bj . Thus, row i participates in at most O(log ni )
of the last
P iterations of the algorithm. The total number of comparisons performed is thus at most
O(m + m
i=1 log ni ), as claimed.
P
To show that the algorithm can also be implemented to run in O(m + m
i=1 log ni ) time, we need
to show that we can quickly identify the rows that are long enough to participate in each iteration.
To do that, we sort dlog ni e using bucket sort. This takes only O(m + maxi dlog ni e) time. When a
row loses some of its items, it is easy to move it to the appropriate bucket in O(1) time. In each
13

iteration we may need to examine
Prows in one bucket that turn out not to be long enough, but this
does not affect the total O(m + m
i=1 log ni ) running time of the algorithm.
Theorem 4.3 Let A be a row-sorted matrix containing m rows, and let N = (n1 , n2 , .P
. . , nm ),
where ni ≥ 1 be the number of items in the i-th row of the matrix, for 1 ≤ i ≤P
m. Let k ≤ m
i=1 ni .
Algorithm Mat-Select3 (A, N, k) selects the k smallest items in A in O(m + m
log
n
)
time.
i
i=1
In Section 4.5 below we show that the running time of P
Mat-Select3 (A, N, k) is optimal for some
values of N = (n1 , n2 , . . . , nm ) and k, e.g., if k = 12 m
The
i=1 ni , i.e., for median selection.
Pm
k
O(m log m ) running time of Mat-Select2 (A, k) is sometimes better than the O(m + i=1 log ni )
running time of Mat-Select3 (A, N, k). We next describe an algorithm, Mat-Select4 (A, k), which
is always at least as fast as the three algorithms already presented, and sometimes faster.

4.4

An O(m +

Pm

i=1

log(ki + 1)) algorithm

As before, let ki be the (yet unknown) number of items in the i-th row that belong to the smallest k
items ofPthe matrix. In this section we describe an algorithm for finding these ki ’s that runs in
O(m + m
i=1 log(ki + 1)) time.
We partition each row this time into blocks of size 1, 2, 4, . . .. The representative of a block is again
the last item in the block. Note that the first ki items in row i reside in blog(k
Pmi + 1)c complete
blocks, plus one incomplete block, if log(ki + 1) is not an integer. Thus L = i=1 blog(ki + 1)c is
exactly the number of block representatives that belong to the k smallest items of the matrix.
Suppose that ` ≥ L is an upper bound on the true value of L. We can run Mat-Select1 to select the `
smallest block representatives in O(m+`) time. If `i representatives
Pm were selected from
Pmrow i, we let
`
+1
i
ni = 2
−1. We now run Mat-Select3 which runs in O(m+ P
i=1 log ni ) = O(m+
i=1 (`i +1)) =
log(k
+
1)),
as
promised.
O(m + `). Thus, if ` = O(L), the total running time is O(m + m
i
i=1
P
blog(k
+
1)c?
We
simply
try ` = m, 2m, 4m, . . .,
How do we find a tight upper bound on L = m
i
i=1
until we obtain a value of ` thatP
is high enough. If ` < L, i.e., ` is not large enough, we can discover
it in one of two ways. Either m
i=1 ni < k, in which case ` is clearly too small. Otherwise, the
algorithm returns an array of ki values. We can check whether these values are the correct ones in
O(m) time. First compute M = maxm
i=1 Ai,ki . Next check that Ai,ki +1 > M , for 1 ≤ i ≤ m. As `
is doubled in each iteration, the
cost
of the last iteration dominates the total running time which
Pm
is thus O(m + 2L) = O(m + i=1 log(ki + 1)). We call the resulting algorithm Mat-Select4 .
Theorem 4.4 Let A be a row-sorted matrix containing m rows
P and let k ≥ 2m. Algorithm
Mat-Select4 (A, k) selects the k smallest items in A in O (m + m
i=1 log(ki + 1)) time, where ki
is the number of items selected from row i.

4.5

Lower bounds for selection from row-sorted matrices

k
We begin with a simple proof that the O(m log m
) algorithm is optimal for k ≥ 2m.

Theorem 4.5 Any algorithm for selecting the k smallest items from a matrix with m sorted rows
must perform at least (m − 1) log m+k
m comparisons on some inputs.
Proof: We use the information-theoretic lower bound. We need to lowerPbound sk (m), which is
the number of m-tuples (k1 , k2 , . . . , km ), where 0 ≤ ki , for 1 ≤ i ≤ m, and m
i=1 ki = k. It is easily

14


seen that sk (m) = m+k−1
m−1 , as this is the number of ways to arrange k identical balls and m − 1
identical dividers in a row. We thus get a lower bound of




m+k−1
m + k − 1 m−1
m+k−1
m+k
log
≥ log
= (m − 1) log
≥ (m − 1) log
,
m−1
m−1
m−1
m

k
where we used the well-known relation nk > nk .
2
Pm
We next show
that our new O(m + i=1 log ni ) algorithm is optimal, at least in some cases, e.g.,
1 Pm
when k = 2 i=1 ni which corresponds to median selection.
P
maTheorem 4.6 Any algorithm for selecting the k = 12 m
i=1 ni smallest
P items from a row-sorted
Pm
trix with m rows of lengths n1 , n2 , . . . , nm ≥ 1 must perform at least m
log(n
+1)−log
(1
+
i
i=1
i=1 ni )
comparisons on some inputs.
Pm
Proof:
The
number
of
possible
solutions
to
the
selection
problem
for
all
values
of
0
≤
k
≤
i=1 ni
Q
(n
+
1).
(Each
solution
corresponds
to
a
choice
0
≤
k
≤
n
,
for
i
=
1,
2,
.
.
.
,
m.)
We
is m
i
i
i
i=1
 Pm

 1 Pm
 prove
below that the number of solutions is maximized for k = 12 Q
n
n
(and
k
=
i=1 i
i=1 i ). The
2
P
m
m
number of possible solutions for this value of k is thus at least ( i=1 (ni + 1))/(1 + i=1 ni ). Taking
logarithm, we get the promised lower bound.
 1 Pm

We next prove that the number of solutions is maximized
when
k
=
n
. Let Xi be a
i
i=1
2
Pm
uniform random variable on {0, 1, . . . , ni }, and let Y = i=1 Xi . The number of solutions for a
P
given value k is proportional to the probability that Y attains the value k. Let Yj = ji=1 Xi . We
P
prove by induction on j that the distribution of Yj is maximized at µj = 21 ji=1 ni , is symmetric
around µj , and is increasing up to µj and decreasing after µj . The base case is obvious as Y1 = X1 is
a uniform distribution. The induction step follows from an easy calculation. Indeed, Yj = Yj−1 +Xj ,
where Xj is uniform and Yj−1 has the required properties. The distribution of Yj is the convolution
of the distributions of Yj−1 and Xj , which corresponds to taking the average of nj + 1 values of the
distribution of Yj−1 . It follows easily that Yj also has the required properties.
2
Pm
Pm
We next compare
Pmthe lower bound obtained, i=1 log(ni + 1) − log (1 + i=1 ni ), with the upper
bound O(m + i=1 log ni ). The subtracted term in the lower bound is dominated by the first
P
log(m+1) Pm
term, i.e., log (1 + m
i=1 ni ) ≤
i=1 log(ni + 1), where equality holds only if ni = 1, for
m
every
i.
When
the
n
’s
are
large,
the
subtracted
term becomes negligible. Also, as ni ≥ 1, we have
i
Pm
i=1 log(ni +1) ≥ m. Thus, the lower and upper bound are always within a constant multiplicative
factor of each other.
Pm
The optimality of the
O(m
+
i=1 log ni ) algorithm also implies the optimality of our new “outputPm
sensitive”
P O(m + i=1 log(ki + 1)) algorithm. As ki ≤ ni , an algorithm that performs less than
c(m + m
on all inputs, for some small enough c, would contradict the
i=1 log(ki + 1)) comparisons
P
lower bounds for the O(m + m
log
ni ) algorithm.
i=1

5

Selection from X + Y

We are given two unsorted sets X and Y and we would like to find the k-th smallest item, and the
set of k smallest items, in the set X + Y . We assume that |X| = m, |Y | = n, where m ≥ n.

15

5.1

An O(m + n + k) algorithm

Heapify X and heapify Y , which takes O(m + n) time. Let x1 , . . . , xm be the heapified order of X,
i.e., xi ≤ x2i , x2i+1 , whenever the respective items exists. Similarly, let y1 , . . . , yn be the heapified
order of Y . Construct a heap of maximum degree 4 representing X + Y as follows. The root
is x1 + y1 . Item xi + y1 , for i ≥ 1 has four children x2i + y1 , x2i+1 + y1 , xi + y2 , xi + y3 . Item
xi + yj , for i ≥ 1, j > 1, has two children xi + y2j , xi + y2j+1 , again when the respective items
exist. (Basically, this is a heapified version of X + y1 , where each xi + y1 is the root of a heapified
version of xi + Y .) We can now apply algorithm Soft-Select on this heap. We call the resulting
algorithm X+Y-Select1 (X, Y ).
Theorem 5.1 Let X and Y be unordered sets of m and n items respectively. Then, algorithm
X+Y-Select1 (X, Y ) finds the k-th smallest item, and the set of k smallest items in X + Y , in
O(m + n + k) time.

5.2

k
An O(m log m
) algorithm, for k ≥ 6m, m ≥ n

If Y is sorted, then X + Y is a row-sorted matrix, and we can use algorithm
k
+ n log n)
Theorem 4.2. We can sort Y in O(n log n) time and get an O(m log m
k
ε
running time of this algorithm is O(m log m ) when k ≥ mn , for any fixed ε > 0.
values of m, n and k, e.g., m = n and k = mno(1) , the cost of sorting is dominant.
that the sorting can always be avoided.

Mat-Select2 of
algorithm. The
But, for certain
We show below

k
We first regress and describe an alternative O(m log m
) algorithm for selection from row-sorted
matrices. The algorithm is somewhat more complicated than algorithm Mat-Select2 given in
Section 4.2. The advantage of the new algorithm is that much less assumptions are made about
the order of the items in each row. A similar approach was used by Frederickson and Johnson [12]
but we believe that our approach is simpler. In particular we rely on a simple partitioning lemma
(Lemma 5.3 below) which is not used, explicitly or implicitly, in [12].

Instead of partitioning each row into blocks of equal size, as done by algorithm Mat-Select2 of
Section 4.2, we partition each row into exponentially increasing blocks, similar, but not identical,
to the partition made by algorithm Mat-Select3 of Section 4.3.
 k 
Let b = 3m
. Partition each row into blocks of size b, b, 2b, 4b, . . . , 2j b, . . .. The representative
of a block is again the last item in the block. We use algorithm Mat-Select1 to select the m
smallest representatives. This takes O(m) time. Let e1 < e2 < . . . < em denote the m selected
representatives in (the unknown) sorted order, and let s1 , s2 , . . . , sm be the sizes of their blocks. We
next use an O(m) weighted selection
P algorithm (see, e.g., Cormen et al. [7], Problem 9.2, p. 225) to
find the smallest ` such that k6 ≤ `j=1 sj and the items e1 , e2 , . . . , e` , in some order. Such an ` ≤ m
 k 
P
k
must exist, as m 3m
− 1) = 31 (k − 3m) ≥ k6 , as k ≥ 6m. Also note that k6 ≤ `j=1 sj < k3 ,
≥ m( 3m
P
P
as the addition of each block at most doubles the total size, i.e., `j=1 sj < 2 `−1
j=1 sj , for ` > 1.
Claim 5.2 All items of the blocks whose representatives are e1 , e2 , . . . , e` are among the k smallest
items in the matrix.
Proof: Let Sk be the set of k smallest items of the matrix.
Consider again the partition of Sk

k
≤ k3 of the items of Sk belong to rows
among the m rows of the matrix. Less than mb = m 3m
that do not contain a full block of Sk items. Thus, at least 2k
3 of the items of Sk are contained in
rows that contain at least one full block of Sk items. The exponential increase in the size of the
blocks ensures that in each such row, at least half of the items of Sk are contained in full blocks.
16

Figure 8: Partitions of Y for n = 32.
Thus, at least k3 of the items of Sk are contained in full blocks. In particular, if e1 , e2 , . . . , e` are the
P
smallest block representatives, and `j=1 sj ≤ k3 , then all the items in the blocks of e1 , e2 , . . . , e`
belong to Sk .
2
We can thus
P remove all the items in the blocks of e1 , e2 , . . . , e` from the matrix and proceed to find
the k − `j=1 sj ≤ 5k
6 smallest items of the remaining matrix. When k drops below 6m, we use
k
) iterations,
the algorithm of Mat-Select1 of Section 4.1. The resulting algorithm performs O(log m
k
each taking O(m) time, so the total running time is O(m log m ). (This matches the running time
of Mat-Select2 , using a somewhat more complicated algorithm.)
k
) algorithm before returning to the seWe make another small adaptation to the new O(m log m
 k 
lection from X + Y problem. Instead of letting b = 3m and using blocks of size b, b, 2b, 4b, . . .,
we let b0 = 2blog2 bc , i.e., b0 is the largest power of 2 which is at most b, and use blocks of size
b0 , b0 , 2b0 , 4b0 , . . .. All block sizes are now powers of 2. As the sizes of the blocks may be halved, we
select the 2m smallest block representatives. The number of items removed from each row in each
iteration is now also a power of 2.

Back to the X + Y problem. The main advantage of the new algorithm is that we do not really
need the items in each row to be sorted. All we need are the items of ranks b, b, 2b, 4b, . . ., where
b = 2` for some ` > 0, in each row. In the X + Y problem the rows, or what remains of them after
a certain number of iterations, are related, so we can easily achieve this task.
At the beginning of the first iteration, we use repeated median selection to find the items of Y
whose ranks are 1, 2, 4, . . .. This also partitions Y into blocks of size 1, 2, 4, . . . such that items of
each block are smaller than the items of the succeeding block. We also place the items of ranks
1, 2, 4, . . . in their corresponding places in Y . This gives us enough information to run the first
iteration of the matrix selection algorithm.
In each iteration, we refine the partition of Y . We apply repeated median selection on each block
of size 2` in Y , breaking it into blocks of size 1, 1, 2, 4, . . . , 2`−1 . The total time needed is O(n) per
iteration, which we can easily afford. We assume for simplicity that n = |Y | is a power of 2 and
that all items in Y are distinct. We now have the following fun lemma:

17

Lemma 5.3 After i iterations of the above process, if 1 ≤ r ≤ n has at most i 1’s in its binary
representation, then Y [r] is the item of rank r in Y , i.e., Y [1 : r − 1] < Y [r] < Y [r + 1 : n].
Additionally, if r1 < r2 both have at most i 1’s in their binary representation, and r2 is the smallest
number larger than r1 with this property, then Y [1 : r1 ] < Y [r1 + 1 : r2 ] < Y [r2 + 1 : n], i.e., the
items in Y [r1 + 1 : r2 ] are all larger than the items in Y [1 : r1 ] and smaller than the items in
Y [r2 + 1 : n].
For example, if n = 32, then after the first iteration we have the partition
Y [1], Y [2], Y [3 : 4], Y [5 : 8], Y [9 : 16], Y [17 : 32] .
After the second iteration, we have the partition
Y [1], Y [2], Y [3], Y [4], Y [5], Y [6], Y [7 : 8], Y [9], Y [10], Y [11:12], Y [13 : 16],
Y [17], Y [18], Y [19 : 20], Y [21 : 24], Y [25 : 32] .
(Actually, blocks of size 2 are also sorted.) The partitions obtained for n = 32 in the first five
iterations are also shown in Figure 8.
Proof: The claim clearly holds after the first iteration, as numbers with a single 1 in their binary
representation are exactly powers of 2. Let Y [r1 +1 : r2 ] be a block of Y generated after i iterations.
If r1 has less than i 1’s, then r2 = r1 + 1, so the block is trivial. Suppose, therefore, that r1 has
exactly i 1’s in its representation and that r2 = r1 + 2` . (` is actually the index of the rightmost 1
in the representation of r1 , counting from 0.) In the (i + 1)-st iteration, this block is broken into
the blocks Y [r1 + 1], Y [r1 + 2], Y [r1 + 3 : r1 + 4], . . . , Y [r1 + 2`−1 + 1 : r1 + 2` ]. As the numbers
r1 + 2j , for 1 ≤ j < ` are exactly the number between r1 and r2 with at most i + 1 1’s in their
binary representation, this establishes the induction step.
2
After i iterations of the modified matrix selection algorithm applied to an X + Y instance, we have
removed a certain number of items di from each row. The number of items removed from each
row in each iteration is a power of 2. By induction, di has at most i 1’s in its representation. In
the (i + 1)-st iteration we set b = 2` , for some ` ≥ 1 and need the items of rank b, 2b, 4b, . . . from
what remains of each row. The items needed from the i-th row are exactly X[i] + Y [di + 2j b], for
j = 0, 1, . . .. The required items from Y are available, as di + 2j b has at most i + 1 1s in its binary
representation! We call the resulting algorithm X+Y-Select2 (X, Y ).
Theorem 5.4 Let X and Y be unordered sets of m and n items respectively, where m ≥ n, and
let k ≥ 6m. Algorithm X+Y-Select2 (X, Y ) finds the k-th smallest item, and the set of k smallest
k
items in X + Y , in O(m log m
) time.

6

Concluding remarks

We used soft heaps to obtain a very simple O(k) algorithm for selecting the k-th smallest item
from a binary min-heap, greatly simplifying the previous O(k) algorithm of Frederickson [11]. We
used this simple heap selection algorithm to obtain simpler algorithms for selection from row-sorted
matrices and from X + Y , simplifying results of Frederickson and Johnson [12]. The simplicity of
our algorithms allowed us to go one
P step further and obtain some improved algorithms for these
problems, in particular an O(m + m
i=1 log(ki + 1)) “output-sensitive” algorithm for selection from
row-sorted matrices.
Our results also demonstrate the usefulness of soft heaps outside the realm of minimum spanning
tree algorithms. It would be nice to find further applications of soft heaps.
18

References
[1] Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre
Tarjan. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448–461, 1973.
[2] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John
Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions,
and X + Y . Algorithmica, 69(2):294–314, 2014.
[3] Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz. Online sorted
range reporting. In Algorithms and Computation, 20th International Symposium, ISAAC 2009,
Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, pages 173–182, 2009.
[4] Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, and J. Ian Munro. Sorting
under partial information (without the ellipsoid algorithm). Combinatorica, 33(6):655–697,
2013.
[5] Bernard Chazelle. A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM, 47(6):1028–1047, 2000.
[6] Bernard Chazelle. The soft heap: an approximate priority queue with optimal error rate. J.
ACM, 47(6):1012–1027, 2000.
[7] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction
to Algorithms, 3rd Edition. MIT Press, 2009.
[8] Dorit Dor and Uri Zwick. Selecting the median. SIAM J. Comput., 28(5):1722–1758, 1999.
[9] Dorit Dor and Uri Zwick. Median selection requires (2 + )n comparisons. SIAM J. Discrete
Math., 14(3):312–325, 2001.
[10] David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28(2):652–673, 1998.
[11] Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput.,
104(2):197–214, 1993.
[12] Greg N. Frederickson and Donald B. Johnson. The complexity of selection and ranking in
X + Y and matrices with sorted columns. J. Comput. Syst. Sci., 24(2):197–208, 1982.
[13] Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking: Sorted
matrices. SIAM J. Comput., 13(1):14–30, 1984.
[14] Greg N. Frederickson and Donald B. Johnson. Erratum: Generalized selection and ranking:
Sorted matrices. SIAM J. Comput., 19(1):205–206, 1990.
[15] Michael L. Fredman. How good is the information theory bound in sorting? Theor. Comput.
Sci., 1(4):355–361, 1976.
[16] Joseph L. Hodges Jr and Erich L. Lehmann. Estimates of location based on rank tests. The
Annals of Mathematical Statistics, pages 598–611, 1963.
[17] Donald B. Johnson and Samuel D. Kashdan. Lower bounds for selection in X + Y and other
multisets. J. ACM, 25(4):556–570, 1978.
[18] Donald B. Johnson and Tetsuo Mizoguchi. Selecting the k-th element in X + Y and X1 + X2 +
. . . + Xm . SIAM J. Comput., 7(2):147–153, 1978.
19

[19] Jeff Kahn and Jeong Han Kim. Entropy and sorting. J. Comput. Syst. Sci., 51(3):390–399,
1995.
[20] Jeff Kahn and Michael Saks. Balancing poset extensions. Order, 1(2):113–126, 1984.
[21] Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for
k-SUM and related problems. CoRR, abs/1705.01720, 2017.
[22] Haim Kaplan, Robert Endre Tarjan, and Uri Zwick. Soft heaps simplified. SIAM J. Comput.,
42(4):1660–1673, 2013.
[23] Bernard O. Koopman. The optimum distribution of effort. Journal of the Operations Research
Society of America, 1(2):52–63, 1953.
[24] Jean-Luc Lambert. Sorting the sums (xi + yj ) in O(n2 ) comparisons. Theoretical Computer
Science, 103(1):137–141, 1992. 7th Annual Symposium on Theoretical Aspects of Computer
Science (STACS 90) (Rouen, 1990).
[25] Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm. J.
ACM, 49(1):16–34, 2002.
[26] Arnold Schönhage, Mike Paterson, and Nicholas Pippenger. Finding the median. J. Comput.
Syst. Sci., 13(2):184–199, 1976.
[27] William L. Steiger and Ileana Streinu. A pseudo-algorithmic separation of lines from pseudolines. Inf. Process. Lett., 53(5):295–299, 1995.
[28] J.W.J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7:347–348, 1964.

20

