建堆的時間複雜度為什麼是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個數、實現優先隊列等。