时间复杂度：O(nlogn)
堆：一种特殊的完全二叉树
满二叉树：一个二叉树，如果每一个层的节点数都达到最大值，并且所有叶子节点都在同一层，则这个二叉树就是满二叉树
完全二叉树：叶结点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
1）大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
2）小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
大根堆：
小根堆：
堆的向下调整性质：
当根节点的左右子树都是堆时，但根本身不满足堆的性质，可以通过一次向下调整来将其变换成一个堆。
堆排序的过程：
1：建立一个堆
2：得到堆顶元素，为最大元素
3：去掉堆顶，将堆最后一个元素放到堆顶，此时可以通过一次调整重新使堆有序
4：堆顶元素为第二大元素
5：重复步骤3，直到堆变空
python实现
-
import random
-
def sift(li, low, high):
-
"""这个是堆的调整函数——保证得到的是大根堆
-
:param li: 列表
-
:param low: 堆的根节点位置
-
:param high: 堆的最后一个元素的位置
-
"""
-
i = low
# i开始指的是根节点所在的位置index
-
j = i *
2 +
1
# j开始指的是i的左孩子
-
tmp = li[low]
# 把堆顶存起来
-
while j <= high:
# 只要j的位置有数据，就要进入循环进行对比
-
if j +
1 <= high
and li[j+
1] > li[j]:
# 如果右孩子有且比较大
-
j +=
1
# j指向右孩子
-
if li[j] > tmp:
# 孩子的值是否比堆顶的值大
-
li[i] = li[j]
-
i = j
# 往下看一层
-
j = i *
2 +
1
-
else:
# tmp的数值更大，把tmp放到i的位置上
-
li[i] = tmp
# 把tmp放到某一级领导位置上
-
break
-
else:
-
li[i] = tmp
# 把tmp放到叶子节点上
-
def heap_sort(li):
-
"""
-
(n-2)//2来源：n是堆的长度，n-1就是最后一个节点的下标，
-
从下标找父节点的公式：（i-1)//2 ,此处的i=n-1
-
:param li: 待排序列表
-
:return:
-
"""
-
n = len(li)
-
for i
in range((n
-2)//
2,
-1,
-1):
-
# 从最后一个节点开始倒着遍历，range是前包后不包，
-
# 所以第一个-1代表可以遍历到第0个位置，倒着遍历，所以步长是-1
-
# i代表建堆时需要调整的部分的根节点的下标
-
sift(li, i, n
-1)
-
# 建堆完成了
-
# print("*", li)
-
for i
in range(n
-1,
-1,
-1):
-
# i指向当前堆的最后一个元素
-
li[
0], li[i] = li[i], li[
0]
-
sift(li,
0, i -
1)
# i-1是新的high
-
li = [i
for i
in range(
10)]
-
random.shuffle(li)
-
print(li,
"\n**")
-
heap_sort(li)
-
print(li)
python内置模块实现了heapq 是小根堆
有两种方式创建堆：
1. 使用一个空列表，用 heapq.heappush()函数把值加入堆中。
2. 使用 heap.heapify(list) 把列表转换成堆结构。
堆的应用
比如求最大/小的元素，top K 之类的问题，这时候堆排序的优势就出来了。用堆排序在 N 个元素中找到 top K，时间复杂度是 O(N log K)，空间复杂度是 O(K)。冒泡插入等排序算法是按线性顺序排列的，是 O(n)的复杂度（需要对 n 个数据进行移位处理）,堆排序利用的是完全二叉树，所以更高效。
heapq 的一些常用方法：
1. heapify(list)，将列表转换为小根堆的数据结构。
2. heappush(heap, x)，将 x 加入堆中。
3. heappop(heap)，从堆中弹出最小的元素。
4. heapreplace(heap, x)，弹出最小的元素，并将 x 加入堆中。
5. heappushpop(heap, x)，先把 x 加入堆中，再弹出最小的元素。
6. heapq.nlargest(n, heap)，返回 heap 中前 n 个最大的元素。
7. heapq.nsmallest(n, heap)，返回 heap 中前 n 个最小的元素。
-
import heapq
-
"""方法一"""
-
nums = [
2,
3,
5,
1,
54,
23,
132]
-
heap = []
-
for num
in nums:
-
heapq.heappush(heap, num)
# 加入堆
-
print(heap)
# [1, 2, 5, 3, 54, 23, 132]
-
"""方法二"""
-
nums = [
2,
3,
5,
1,
54,
23,
132]
-
heapq.heapify(nums)
-
print(nums)
# [1, 2, 5, 3, 54, 23, 132]
-
"""用 heappop 实现堆排序"""
-
print([heapq.heappop(nums)
for _
in range(len(nums))])
-
# out: [1, 2, 3, 5, 23, 54, 132]
转载：https://blog.csdn.net/FRBeVrQbN4L/article/details/109663988