>假设我正在接收两个整数流。每个整数流 （1） 不保证按递增顺序排列，并且 （2） 偶尔，第一个流中会缺少 1 个或多个整数，但存在于第二个流中。例如：
流 1 - 1, 2, 3, 5, 4, 6, 8, 9, 10, ...
流 2 - 1, 2, 3, 4, 5, 6, 8, 7, 10, ...
什么是具有低时空复杂度的数据结构和/或算法，用于构造包含两个流的并集（即删除重复项）集中的每个整数的排序流？那是：
已排序的流 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
当然，天真的方法是存储每个结果，然后在 O（n log n 中排序），在线性扫描中进行最后的扫描以删除所有连续的重复元素。但这需要大量内存，并且需要两个流在开始任何处理之前终止。
这是针对嵌入式设备上的UDP数据包序列器，因此最好使用C语言的代码片段，但我也可以阅读Python。
我们对得到的整数一无所知，还是它们只是任意的？
您将需要在某个时候进行排序，因此我看不到避免O（n lg n）的方法。您最好的选择是专为随用随选方法而设计的堆排序。如果该值已经存在，请不要添加它。
（显然，您每次都会向堆中添加一个元素，而不是排序。