arrays - 如何在不相交的$ C $排序数组的联合中找到$ k $个最小项？

这里有一个解释，但我觉得很不清楚。
对于如何在$c$不相交的排序数组中找到第$k$个最小的项，是否有一个更严格、更容易理解的算法？

最佳答案

基本上，在任何给定的时间，我们都必须同时比较所有数组中最小的项，找到最小的项，然后增量地更新它基本上我们想要一堆。
设A[i]为第i个数组，A[i][j]为该数组的第j个元素排序以便[i][0]是第i个数组中的最小值。设h为最小堆，设i为另一个长度为c的数组。

I = [0] * C
array = [(A[i][0], i) for i in range(C)]
H = heapify(array)

在堆中，元组按字典方式排序，即元组中的第一个元素排序。接下来，我们要做的是：

for i in range(k-1):
    z = H.peek()[1] # which array smallest came from
    I[z] += 1 # update index for that array
    H.replace((A[z][I[z]], z)) # remove smallest, update

k_smallest = H.peek()[0]

这是python，只是我假装python有一个很好的堆其思想是维护一个大小等于数组数量的堆，每个数组中的当前元素最小。每次我们弹出最小的元素，然后从数组中获取下一个元素这样，每个数组在堆中总是有一个“代表”，并且我们总是确信堆的顶部是所有未处理元素中最小的。我们丢弃了第一个k-1，然后偷看kth。
运行时间：堆操作将花费o（log（c）），您将不得不执行k次，所以o（klog（c））。但是，您还必须首先创建堆，因此它总计为o（klog（c）+c）。
编辑：由于堆的创建，我以前的解决方案实际上是O（（k+C）log（C））我现在把堆创建改为一个“heapify”，只需花费C。