Authors: Michael Cao, Benjamin Qi
A way to merge two sets efficiently.
Obviously linked lists can be merged in time. But what about sets or vectors?
Focus Problem – read through this problem before continuing!
Let's consider a tree rooted at node , where each node has a color.
For each node, let's store a set containing only that node, and we want to merge the sets in the nodes subtree together such that each node has a set consisting of all colors in the nodes subtree. Doing this allows us to solve a variety of problems, such as query the number of distinct colors in each subtree.
Suppose that we want merge two sets and of sizes and , respectively. One possiblility is the following:
1for (int x: b) a.insert(x);
which runs in time, yielding a runtime of in the worst case. If we instead maintain and as sorted vectors, we can merge them in time, but is also too slow.
With just one additional line of code, we can significantly speed this up.
1if (a.size() < b.size()) swap(a,b);2for (int x: b) a.insert(x);
Note that swap exchanges two sets in time. Thus, merging a smaller set of size into the larger one of size takes time.
Claim: The solution runs in time.
Proof: When merging two sets, you move from the smaller set to the larger set. If the size of the smaller set is , then the size of the resulting set is at least . Thus, an element that has been moved times will be in a set of size at least , and since the maximum size of a set is (the root), each element will be moved at most ) times.
A set doesn't have to be an
std::set. Many data structures can be merged, such as
std::swap doesn't necessarily work in time; for example, swapping two arrays takes time linear in the sum of the sizes of the arrays, and the same goes for indexed sets. For two indexed sets
b we can use
a.swap(b) in place of
This section is not complete.
It's easy to merge two sets of sizes in or time, but sometimes can be significantly better than both of these. Check "Advanced - Treaps" for more details. Also see this link regarding merging segment trees.