建堆的时间复杂度为什么是O(nlogn)

一、证明建堆的时间复杂度为O(nlogn)

对于堆的构建，我们需要经过heapify调整操作。我们把构建一个大小为N的堆中所有非终端节点调整的时间称为一次heapify的执行时间，则对于一次heapify的操作，时间复杂度为log(n)。

假设我们已经完成了对整个堆的所有非叶子节点的heapify操作，我们仍然需要对底层叶子节点进行排列。每个叶子节点heapify的时间复杂度是0，由于有N个叶子节点，所以对于所有堆操作的时间复杂度为O(NlogN)。

二、建堆时间复杂度

建堆的时间复杂度也就是上面所说的所有堆操作的时间复杂度，即O(NlogN)。

def heapify(arr, n, i):
  largest = i
  l = 2 * i + 1
  r = 2 * i + 2
  if l < n and arr[i] < arr[l]:
    largest = l
  if r < n and arr[largest] < arr[r]:
    largest = r
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def build_heap(arr):
  n = len(arr)
  for i in range(n, -1, -1):
    heapify(arr, n, i)

三、初始建堆的时间复杂度

初始建堆的时间复杂度同样是O(NlogN)。因为我们需要对堆中的每个元素进行调整heapify操作，对每个元素而言，最坏情况下需要调整的层数是logN。

我们可以利用heapify操作和完全二叉树的性质加速堆的构建过程。直接将一个无序序列构建成堆的时间复杂度是O(NlogN)，但是如果我们从第N/2个节点（该节点的父节点为N/4，满足所有父节点大于其子节点）开始heapify调整，由于完全二叉树节点大部分都是叶子节点，所以这些节点heapify操作后不会影响其他的节点。因此，如果我们从下往上调整，整个维护堆时间复杂度就降为了O(N)。

def heapify(arr, n, i):
  largest = i
  l = 2 * i + 1
  r = 2 * i + 2
  if l < n and arr[i] < arr[l]:
    largest = l
  if r < n and arr[largest] < arr[r]:
    largest = r
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def build_heap(arr):
  n = len(arr)
  for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)

四、归并排序的时间复杂度

归并排序时间复杂度为O(nlogn)。它使用了分治思想：将一个大问题分为一个或多个更小的子问题，直到子问题可以使用直接计算的方式求解，然后将所有子问题的解合并起来得到大问题的解。

归并排序的核心思想是将一组未排序的元素划分为越来越小的子集，再将各个子集排序并合并成较大的有序集合，直到最后只剩下一个排序完成的集合。

def merge_sort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    merge_sort(left)
    merge_sort(right)
    i = j = k = 0
    while i < len(left) and j < len(right):
      if left[i] < right[j]:
        arr[k] = left[i]
        i += 1
      else:
        arr[k] = right[j]
        j += 1
      k += 1
    while i < len(left):
      arr[k] = left[i]
      i += 1
      k += 1
    while j < len(right):
      arr[k] = right[j]
      j += 1
      k += 1

五、快速排序的时间复杂度

快速排序时间复杂度在最坏情况下为O(n^2)；在平均情况下表现良好，为O(nlogn)。

快速排序的核心思想是选择一个元素作为pivot，将整个数组划分成左右两个子数组，使得左边的元素都小于pivot，右边的元素都大于pivot，然后对左右子数组分别进行排序。

在最坏情况下，pivot每次都是数组中最大或最小的元素，并且每次都只划分出一个子数组，快速排序就会变成冒泡排序，时间复杂度为O(n^2)。

def quick_sort(arr, left, right):
  if left < right:
    pivot_index = partition(arr, left, right)
    quick_sort(arr, left, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, right)

def partition(arr, left, right):
  pivot = arr[right]
  i = left - 1
  for j in range(left, right):
    if arr[j] < pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[right] = arr[right], arr[i + 1]
  return i + 1

六、堆的复杂度

堆数据结构的操作复杂度如下：

• 建堆的时间复杂度为O(n)，这是通过下面提到的bottom-up heap construction实现的。
• 添加元素的时间复杂度为O(logn)，因为我们只需要添加到堆的最后，然后逐步向上调整元素。
• 获取最大（小）值并删除的时间复杂度为O(logn)，由于我们需要从堆顶获取最大/小值，然后将堆的最后一个元素移动到堆顶并进行heapify操作。
• 获取最大（小）值但是不删除的时间复杂度为O(1)，我们只需要返回堆的根节点。

七、堆排序的时间复杂度

堆排序时间复杂度为O(nlogn)。

使用堆排序的基本思路是通过堆数据结构构建一个最大堆/最小堆，然后将堆的根节点与堆的最后一个节点交换，取出堆的最后一个节点，对新的堆进行heapify操作，直到堆为空，所有节点都已经进行了排序。

def heap_sort(arr):
  n = len(arr)
  for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
  for i in range(n - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)

八、数组建堆时间复杂度

由于数组不像二叉堆有左右孩子节点的关系，所以它需要其他方法来实现建堆，使用数组实现堆的时间复杂度为O(N)。

数组建堆的思路是对于任意结点i，如果它有左右孩子节点，那么孩子节点比结点i的编号都要大，这样我们就可以通过一个线性数据结构解决类似二叉树结构的问题。

def heapify(arr, n, i):
  largest = i
  l = 2 * i + 1
  r = 2 * i + 2
  if l < n and arr[i] < arr[l]:
    largest = l
  if r < n and arr[largest] < arr[r]:
    largest = r
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def build_heap(arr):
  n = len(arr)
  for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)

九、最小堆构建时间复杂度

和最大堆一样，最小堆的构建时间复杂度同样为O(NlogN)。

最小堆是指根节点的键值最小。由于我们需要排序所有元素并构建二叉堆，所以时间复杂度与最大堆构建相同。

十、最大堆时间复杂度

最大堆的构建时间复杂度为O(NlogN)。

和最小堆类似，最大堆的构建时间复杂度也与元素总数相关。在堆的构建过程中，维护堆的时间复杂度为O(NlogN)。

结束语

建堆的时间复杂度很大程度上决定了堆排序的时间复杂度，堆排序是一种基于比较的排序算法。由于它使用了堆数据结构，可以实现O(nlogn)的时间复杂度，堆排序的空间复杂度是O(1)。

除了堆排序，堆数据结构还有许多常见的应用。例如，求最大k个数、实现优先队列等。