堆是具备以下特征的一种特殊二叉树：
1、是一棵完全二叉树
2、每个节点的值均小于（大于）或等于它的两个孩子节点（如果存在）的值。
3、树根节点（称为堆顶元素）的值最小（称为小顶堆）或最大（成为大顶堆）。
所以，堆顶元素（即第一个元素）必为最大值（或最小值）。
堆树例子：
86
_____/ \_______
/ \
42 80
_/ \_ _/ \_
/ \ / \
18 32 51 25
/
12
堆排序步骤：
1、转换成完全二叉树
例：list_datas = [88, 6, 57, 72, 60, 42, 83, 73, 48, 85]
数组从左到右按二叉树层次遍历方式填充到二叉树中:
88
_____/ \_______
/ \
6 57
_/ \_ _/ \_
/ \ / \
72 60 42 83
/ \ /
73 48 85
但这里并不是要真的建立Node组成二叉树，用数组表示二叉树就行了。
由于是按一定规则填充到二叉树上的，那么在数组中，就会存在数学规律，
不难发现，每个数的左右孩子分别为 2i + 1、2i + 2, i 为 该数在数组中的下标值，
因此，不需要单独储存二叉树，仅使用数学公式就够了。
2、建堆（将完全二叉树调整为堆）：对于有n个节点的完全二叉树，可按如下步骤，使其调整为堆：
① 从中间(位置 n/2 - 1，可以证明为最后一个非叶子节点)节点开始调整；
② 找出以此节点作为父节点的两个孩子节点的较小值（若建大顶堆则选较大值）,并与父结点比较，
若小于（大于）父节点，则与父节点进行交换。然后，以交换后的子节点作为父节点。重复此步骤
直到没有了子节点(即叶子节点).
③ 把步骤②中原来父节点的位置往前推一个位置，作为新的父节点。重复步骤②，直到根节点为止，
此时完全二叉树将成为一个堆，根节点(即数组第一个值)则是最大值（或最小值）。
3、取堆顶，并用堆底代替堆顶
4、重复 2、3
演示完全二叉树建成小顶堆的过程：
[88, 6, 57, 72, 60, 42, 83, 73, 48, 85]
88
_____/ \_______
/ \
6 57
_/ \_ _/ \_
/ \ / \
72 60 42 83
/ \ /
73 48 85
INFO: n = 10, 取位置 i = (n // 2) - 1 = 4（即60，是最后一个非叶子节点）作为第一个节点。
INFO: 根据公式 2i + 1, 2i + 2 推算左右孩子节点，即9， 10，10 超过最大下标9，说明没有右孩子。
INFO: 60 < 85, 不需要调换顺序，i -= 1 = 3, 节点换到 72，
判断 72，73，48， 最小是48，需要把72，48调换顺序，
数组变成：[88, 6, 57, 48, 60, 42, 83, 72, 48, 85]
88
_____/ \_______
/ \
6 57
_/ \_ _/ \_
/ \ / \
48 60 42 83
/ \ /
73 72 85
INFO: 新节点变成交换后的子节点， i = 8, 值72，根据公式 2i + 1, 2i + 2 推算无左右孩子节点， i -= 1
INFO: i=7, 依然无左右孩子， i -= 1
INFO: i=6, i=5, 都无左右孩子，i -= 1
INFO: i 回到 4，但无需调整, i -= 1;
INFO: i 回到 3，但无需调整, i -= 1;
INFO: i=2，调整 42、57
数组变成：[88, 6, 42, 48, 60, 57, 83, 72, 48, 85]
88
_____/ \_______
/ \
6 42
_/ \_ _/ \_
/ \ / \
48 60 57 83
/ \ /
73 72 85
INFO: 继续重复操作后最后变成
[6, 48, 42, 72, 60, 57, 83, 73, 88, 85]
6
_____/ \_______
/ \
48 42
_/ \_ _/ \_
/ \ / \
72 60 57 83
/ \ /
73 88 85
INFO: 完成最小堆建立，输出栈顶（6），并把栈底（85）调换到栈顶处：
6
[85, 48, 42, 72, 60, 57, 83, 73, 88]
85
_____/ \_______
/ \
48 42
_/ \_ _/ \_
/ \ / \
72 60 57 83
/ \
73 88
非递归实现
def heap_sort_iteration4(datas):
end_index = len(datas) - 1
while end_index > 0:
i = (end_index + 1) // 2 - 1
while i >= 0:
left, right = 2 * i + 1, 2 * i + 2
max_i = max(i, left, right if right <= end_index else i, key=lambda _i: datas[_i])
if max_i != i:
datas[i], datas[max_i] = datas[max_i], datas[i]
i -= 1
datas[0], datas[end_index] = datas[end_index], datas[0]
end_index -= 1
return datas
递归实现：
def heap_sort_recursion4(datas):
def _bulid_large_heap(end_index):
if end_index == 0:
return
i = (end_index + 1) // 2 - 1
while i >= 0:
left, right = 2 * i + 1, 2 * i + 2
max_i = max(i, left, right if right <= end_index else i, key=lambda _i: datas[_i])
if max_i != i:
datas[i], datas[max_i] = datas[max_i], datas[i]
i -= 1
datas[0], datas[end_index] = datas[end_index], datas[0]
_bulid_large_heap(end_index - 1)
_bulid_large_heap(len(datas) - 1)
return datas