Elr*_*son 2 algorithm data-structures
我遇到了一个类似的问题 Given a million integers, return the kth smallest element。问题下方有一个给定的解决方案，我不确定为什么这是最佳解决方案。给定的解决方案涉及使用最小堆。所以最初，我认为这是有道理的，因为我们可以在恒定时间内找到堆中的最小元素。但在我再思考一秒钟后，我想到了将数组中的元素插入堆中的成本。如果我的理解是正确的，插入是一种O(logN)操作。但是如果我们插入N元素，那么这应该花费我们O(NlogN)时间。我们还为我们正在使用的堆使用了额外的空间。所以我的问题是，为什么这比对数组进行排序并取第 k-1 个索引更好的解决方案？
在最小堆中，单次插入是O(logN) 最坏的情况，因为只有在违反堆属性（父值应小于子值）时才会产生该成本。
有一个定理说，如果要将数组转换为堆（称为构建堆），则总体复杂度为O(N)，而不是O(NlogN)。您可以在Wikipedia 中阅读有关 binary heap的详细信息。
所以这种方法确实比简单地对整个数组进行排序要好。由于对整个数组进行排序的时间复杂度为O(NlogN)，而使用最小堆方法的总复杂度为O(N+klogN)，这在k较小时更为理想。
为了完整起见，我将描述为什么k使用 min-heap取第-th 个最小元素的复杂性是O(N+klogN). 如果你想要最小的元素，你可以在常数时间内取根。但是第二小的元素呢？然后您需要删除最小的元素，然后恢复堆属性。那么根将是数组中最小元素已被删除的最小元素，因此它是第二小的元素。我们可以继续这样做k以获得第k-th 个最小的元素。由于恢复堆属性的操作是O(logN)，所以总的复杂度是O(N+klogN)建立堆然后不断删除最小元素的k次数。