6.堆排序
6.1算法思想
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点（同层节点不进行比较）。并且一般来说，升序排列通过构造大顶堆来实现，降序排列通过构造小顶堆来实现。
这种算法不用额外的空间，空间复杂度为o（1），时间复杂度为o（nlogn）
6.1.1堆
堆是一种完全二叉树（完全二叉树 是 一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树）
堆有两种类型: 大顶堆和小顶堆：
大顶堆：每个结点的值都大于或等于左右孩子结点
小顶堆：每个结点的值都小于或等于左右孩子结点
大顶堆和小顶堆可以通过下面的图进行直观的感受：
6.2 算法过程
- 首先将待排序的数组构造出一个大顶堆（这里以升序排列为例）
- 取出这个大顶堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆。
- 重复第二步，直到这个大根堆的长度为1，此时完成排序
ps：将数组中的元素构造成大顶堆的时候，堆顶元素就是所有元素的最大值，而堆的最下最右是数组的最后一个元素，这就相当于把最大值放在了数组的最后，然后在对剩下的元素进行相同操作。
对于这个算法的具体过程的图示，大家可以看一下堆排序图解这篇博客。
过程动图如下
6.3 python代码
6.3.1 递归（不对原数组引入一个辅助元素）
global
length
# 定义全局变量
def
buildMaxHeap
(
numList
)
:
# 构建最大堆，
global
length
length
=
len
(
numList
)
for
i
in
range
(
length
//
2
,
-
1
,
-
1
)
:
# 从最后一个有子节点的根节点节点开始构建的时候从下往上，从右向左构建
heapify
(
numList
,
i
)
def
heapify
(
numList
,
i
)
:
# 堆调整，将剩下的元素调整成最大堆
global
left
,
right
,
largest
,
length
leftChildren
=
2
*
i
+
1
rightChildren
=
2
*
i
+
2
largest
=
i
if
leftChildren
<
length
and
numList
[
leftChildren
]
>
numList
[
largest
]
:
# leftChildren < length先判断是否有子节点，因为python数组下标从零开始的缘故，下标为length/2的元素可能会没有子节点。
largest
=
leftChildren
if
rightChildren
<
length
and
numList
[
rightChildren
]
>
numList
[
largest
]
:
largest
=
rightChildren
if
largest
!=
i
:
# 如果largest（最大的节点所在的下标），不是根节点，说明这三个借点不满足堆的规则，
# 需要进行调整，根节点的下标是i，最大节点的下标是largest，交换即可。
swap
(
numList
,
i
,
largest
)
# 当当前的根节点和子节点满足堆的关系之后，由子节点作为根节点的树可能又不满足了，必须在对下一层的树进行检查和调整。
heapify
(
numList
,
largest
)
def
swap
(
numList
,
i
,
j
)
:
numList
[
i
]
,
numList
[
j
]
=
numList
[
j
]
,
numList
[
i
]
def
heapSort
(
numList
)
:
global
length
buildMaxHeap
(
numList
)
for
i
in
range
(
len
(
numList
)
-
1
,
0
,
-
1
)
:
swap
(
numList
,
0
,
i
)
length
-=
1
# 在调整的时候就不会在调整最后一个元素了
heapify
(
numList
,
0
)
# 由于交换之前，已经都调整为最大堆了，而交换之后，大部分都符合堆的规则，
# 只从堆顶元素（下标为1）开始，只进行局部的调整就好，
# 这时候不用再像刚开始构建最大堆一样从下往上，从右往左调整交换了。
return
numList
numlist
=
[
4
,
5
,
4
,
1
,
8
,
7
,
2
,
6
,
3
]
print
(
heapSort
(
numlist
)
)
6.3.2非递归（引入一个辅助因素，将数组的下标往后加1）
def
swap
(
arr
,
i
,
j
)
:
arr
[
i
]
,
arr
[
j
]
=
arr
[
j
]
,
arr
[
i
]
def
heapAdjust
(
arr
,
start
,
end
)
:
i
=
start
temp
=
arr
[
start
]
j
=
2
*
i
while
j
<=
end
:
if
j
<
end
and
arr
[
j
]
<
arr
[
j
+
1
]
:
j
+=
1
if
arr
[
i
]
<
arr
[
j
]
:
arr
[
i
]
=
arr
[
j
]
i
=
j
j
=
2
*
i
else
:
break
arr
[
i
]
=
temp
def
heapSort
(
numList
)
:
numList
.
insert
(
0
,
0
)
# 由于python，数组的下标从0开始，因此需要加入一个辅助元素，是所有的元素的下标都往后移动一位。
length
=
len
(
numList
)
-
1
firstAdjustRoot
=
length
//
2
for
i
in
range
(
firstAdjustRoot
)
:
# 在构造最大堆的时候，不会对最左侧的0进行处理，因为i不会取到firstAdjustRoot。
heapAdjust
(
numList
,
firstAdjustRoot
-
i
,
length
)
for
i
in
range
(
length
-
1
)
:
swap
(
numList
,
1
,
length
-
i
)
# 由于大顶堆的堆顶元素是最大的，把它和数组最后的元素（堆的最下层最右元素）
# 进行互换，就相当于把最大值放在了最后，下一次，把最后一个元素撇出来，对剩下来的在排序
heapAdjust
(
numList
,
1
,
length
-
i
-
1
)
# 由于交换之前，已经都调整为最大堆了，而交换之后，大部分都符合堆的规则，
# 只从堆顶元素（下标为1）开始，只进行局部的调整就好，
# 这时候不用再像刚开始构建最大堆一样从下往上，从右往左调整交换了。
return
[
numList
[
i
]
for
i
in
range
(
1
,
len
(
numList
)
)
]
numlist
=
[
50
,
16
,
30
,
10
,
60
,
90
,
2
,
80
,
70
]
print
(
heapSort
(
numlist
)
)
参考文章
有辅助元素的堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.cnblogs.com/onepixel/articles/7674659.html
