获取堆排序的前x个元素

Question

我正在为谷歌开发者面试做准备，并在做算法问题。我需要弄清楚如何获得第一个x元素的大小n的数组使用堆排序算法。算法的哪一部分需要修改才能得到第一个x最小的元素?

这是来自Cormen Leiserson的Introduction to Algorithms(第155页)中的堆排序算法:

HEAPSORT(A)
{
  BUILD-MAX-HEAP(A)
    for i = A.length down to 2
      exchange A[1] with A[i]
      A.heap-size = A.heap-size - 1
      MAX-HEAPIFY(A, 1)
}

这些是组成算法:

BUILD-MAX-HEAP(A)
  A.heap-size = A.length
  for i = floor(A.length / 2) down to 1
    MAX-HEAPIFY(A, i)
MAX-HEAPIFY(A, i)
  l = LEFT(i)
  r = RIGHT(i)
  if l <= A.heap-size and A[l] > A[i]
    largest = l
  else largest = r
  if r <= A.heap-size and A[r] > A[largest]
    largest = r
  if largest != i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A, largest)

我不知道要修改哪一部分来获得排序数组的x最小元素。还需要找出改进算法的时间复杂度

Answer 1

通过更改MAX-HEAPIFY中的条件，我们可以将其更改为min - heapify，因此，我们可以轻松地获得最小堆。

那么，这个堆的第一个元素是最小的元素，我们可以删除这个元素，并把堆中的最后一个元素带到第一个元素，并再次调用MIN-HEAPIFY来维护堆的属性。继续这个过程n次，我们可以得到前n个最小的对象。

时间复杂度:log(m) + log(m - 1) +…+ log(m - n) ~ O(nlogm)