所以我们遇到了一个问题，如果给定一个包含 n 个元素的数组，我们需要从中提取 k 个最小的元素。我们的解决方案应该使用堆，复杂度应该是 O(n + k log n)。我想我可能已经找到了解决方案，但我想确定一下。
我会说数组必须首先使用典型的 buildHeap() 函数构建到堆中，该函数从数组长度的一半开始并调用 minHeapify() 函数以确保每个父级至少小于其长度 children 。总而言之，这将是 O(n) 的复杂性。由于我们需要提取 k 次，因此我们将使用 extractMin() 函数，该函数将删除最小值，并使用 minHeapify() 保留最小堆属性。 extractMin() 将是 O(logn)，并且由于它会完成 k 次，这支持 O(n+klogn) 的整体复杂性。
这个检查出来了吗？有人告诉我它也应该用 heapSort() 函数进行排序，但这对我来说没有意义，因为 heapSort() 会给整体复杂性增加一个 O(nlogn)，而且你仍然能够提取min 没有排序...
最佳答案
是的，你是对的。您不需要 heapSort() 但需要 heapify() 来重新排序您的堆。
关于algorithm - 我对此算法的复杂度 O(n + k log n) 的解释是否正确？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26269243/