预备知识
堆
定义
堆（英语：heap），是计算机科学中的一种特别的完全二叉树，它满足以下性质：
- 给定堆中任意节点P和C，若P是C的母节点，那么P的值总是小于等于（或大于等于）其子节点C的值。
- 除最底层，其它层的节点都填满，且最底层通过从左往右顺序添加元素。
- 逻辑结构为树，存储结构为数组。
分类
根据父节点和儿子节点之间的大小关系，可分为小根堆和大根堆（如下图）：
- 小跟堆：给定堆中任意节点P和C，若P是C的母节点，那么P的值总是小于等于其子节点C的值
- 大根堆：给定堆中任意节点P和C，若P是C的母节点，那么P的值总是大于等于其子节点C的值
基本操作
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| build | 建立一个空堆 | O(n) |
| insert | 向堆中插入一个元素 | O(logn) |
| get | 获取堆顶元素 | O(1) |
| delete | 删除堆顶元素 | O(logn) |
| heapify | 使删除堆顶元素的堆再次成为堆 | O(logn) |
insert操作：
- 将新元素插入到堆的尾部
- 将新元素heapifyup，即依次向上调整整个堆的结构
delete操作： - 将堆尾元素替换掉堆顶元素（实现所谓删除）
- 对堆顶元素heapifydown，即依次向下调整整个堆的结构
用途
建立优先队列、找最值、堆排序等。
算法详解
首先解决一个问题，即为什么我们要进行堆排序？在正常的堆中，数据只是在父子关系的层面上有序，在小跟堆中每个孩子节点都大于它的父节点，在大跟堆中每个孩子节点都小于它的父节点。这种粒度的有序太粗糙，为了达到整体的有序，因此需要排序。
算法过程
以构造一个降序序列为例：
构造降序序列，初始化对应构建小根堆（反之，大根堆）。
一、 将待排序序列构成一个小根堆
- 设初始数组为[6,1,2,3,0,4,5,7]
- 按照完全二叉树，将数字依次填入
- 找到最下面的非叶子节点（第len(nums)//2-1个节点），开始依次调整，即根据小根堆的性质，把每个节点看做根节点，做一次heapifydown，让小元素上浮，大元素下沉
- 从下至上（数组的排列上），从右往左（树的结构上），从最底非叶子节点到根节点，对每个节点做这样的调整
二、 将堆顶元素和末尾元素交换此时末尾元素就是最小值
三、将剩余n-1个元素重新构造成一个小根堆，得到n个元素的第二小值
四、 反复执行二、三步，得到降序有序序列
时间复杂度分析
O(nlogn). 其中，构造小根堆时间复杂度为O(n)，每个元素下沉的时间复杂度为O(logn)，一共有n-1个元素需要下沉，故总共消耗的时间为O(n+(n-1)*logn)，即O(nlogn).
空间复杂度分析
O(1). 堆本身所占用的数组空间n不计算在内（空间复杂度仅计算辅助变量所开辟的空间大小），对于原地排序而言，空间复杂度为O(1).
稳定性分析
不稳定。
代码实现
def heapSort(nums):
n = len(nums)
# 初始建堆，从最后一个非叶子节点往上，依次做heapifyDown
for i in range(n//2 - 1, -1, -1):
heapifyDown(nums, i, n)
# 堆排序（调整堆，使有序）
for i in range(n-1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapifyDown(nums, 0, i)
def heapifyDown(nums, i, n):
lt, rt = 2*i+1, 2*i+2
smallest = i
if lt < n and nums[lt] < nums[smallest]:
smallest = lt
if rt < n and nums[rt] < nums[smallest]:
smallest = rt
if smallest != i:
nums[smallest], nums[i] = nums[i], nums[smallest]
heapifyDown(nums, smallest, n)