一、证明建堆的时间复杂度为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个数、实现优先队列等。
