（二叉）堆的定义

（二叉）堆是一个数组，可以被看成一个近似的完全二叉树。

class MaxHeap:
    def __init__(self, nums: List[int]):
        self.size = len(nums)
        # 堆数组索引从1开始，方便left, right和parent的计算
        self.arr = [0 for _ in range(self.size + 1)]
    def _left(self, i):
        return 2 * i
    def _right(self, i):
        return 2 * i + 1
    def _parent(self, i):
        return i // 2
    # 假定arr[i]的以left(i)和right(i)为根的二叉树
    # 都是最大堆
    def max_heapify(self, i):
        size = self.size
        l, r = self._left(i), self._right(i)
        if l <= size and self.arr[l] > self.arr[i]:
            largest = l
        else:
            largest = i
        if r <= size and self.arr[r] > self.arr[largest]:
            largest = r
        if largest != i:
            self.arr[i], self.arr[largest] = self.arr[largest], self.arr[i]
            # 交换过后可能不是最大堆，所以得维护堆的性质
            self.max_heapify(largest)

堆排序

步骤：

1. 用给定的数组构建一个最大堆
2. 将最大堆的根节点移动到末尾
3. 除去末尾的结点并维护最大堆的性质

4. 重复此过程 ```python def build_max_heap(nums: List[int]) -> MaxHeap: heap = MaxHeap(nums) for i in range(len(nums)):

    heap.arr[i+1] = nums[i]

   默认叶节点是符合最大堆的性质

   for i in range(heap.size // 2, 0, -1):

    heap.max_heapify(i)

   return heap

def heap_sort(nums):

# 也可以原地排序，不过得修改left(i)，right(i)和parent(i)
heap = build_max_heap(nums)
for i in range(heap.size, 1, -1):
    heap.arr[1], heap.arr[i] = heap.arr[i], heap.arr[1]
    heap.size -= 1
    heap.max_heapify(1)
ret = heap.arr[1:]
return ret

```

性能分析

时间复杂度：

• max_heapify()：（为堆的高度）
• build_max_heap()：
• heap_sort()：