数据结构(python) —— 【11: 堆排序】_向最大堆99,72,76,7,30,41依次插入元素86,91,91,94,97，最终得到的最大堆是

堆排序

    前面讲了堆的向下调整，今天来讲讲怎么利用堆进行排序即堆排序！

1. 步骤

1. 先根据完全二叉树建立堆(农村包围城市)
2. 得到堆顶元素，为最大元素
3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整使堆有序
4. 堆顶元素为第二大元素
5. 重复步骤3，直到堆变空

简单点概括就是先建立堆，再根据前面所学的向下调整函数数据结构(python) —— 【10: 堆的向下调整】，将堆从下到上、从小到大依次调整就变为一个大根堆或者小根堆，最后挨个出数，就能排序了！

2. 演示

1. 建立堆

拿以下这个完全二叉树举例:
这个完全二叉树没有任何排列规则，现在我们需要通过向下调整函数把该二叉树变为大根堆( 一颗完全二叉树，满足任一节点都比其孩子节点大)
来看看GIF演示吧:

2. 挨个出数

第一步已经建立好堆，那么现在堆的根结点为最大的数，先把根结点取出，放在列表中，再将堆的最后一个放到堆顶，再进行向下调整，调整后，堆的根结点又是最大数，再次将根结点放入列表，再次将堆的最后一个放到堆顶，重复这些步骤，知道所有的数都放入了列表。
再次用我自己做的GIFA进行演示:

3. 代码

'''
TOP: 堆排序
author: Blue
time: 2020-07-24
QQ: 2458682080
'''

# 堆排序没有递归
# 针对大根堆的调整函数
def sift(li, root, last):
    """
    :param li: 列表
    :param root: 二叉树的根结点的下标
    :param last: 二叉树的最后一个元素的下标
    :return:
    """
    temp = li[root]   # 将根结点暂时储存起来
    i = root  # i最开始指的是根结点
    child = i * 2 + 1  # 先指向左孩子
    while child <= last:   # 只要不到最后一个叶结点
        if child+1 <= last and li[child+1] > li[child]:  #当右孩子>左孩子
            child += 1  # 就把要换上去(要变为空位)的节点变为右孩子
        if li[child] > temp:
            li[i]  = li[child]
            i = child  # 向下看一层
            child = i * 2 + 1  # 继续指向左孩子
        else:    # li[child] > temp 如果目前空位的最大的孩子都比tmep小，那temp就可以放这里
            li[i] = temp
            break
     else:  # 当目前节点在叶结点时
        li[i] = temp

# 堆排序
def heap_sort(li):
    n = len(li)
    # 第一步: 建立堆
    for i in range((n - 2) // 2, -1, -1):    # 因为是从后往前，所以第一个-1是指i可以到列表第一个0 ，第二个-1是步长是
        # i表示建堆的时候调整的部分的根下标
        sift(li, i, n-1)

    # 第二步: 堆建立完成后，开始挨个出数
    for i in range(n - 1, -1, -1):
        # i指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]  # 这里为了节省空间，直接将堆后面不要的空间进行储存，实在不理解的读者可以自己新建一个列表储存拿出来的值
        sift(li, 0, i - 1)   # i-1是新的last

li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

结果为:

[33, 74, 48, 29, 37, 7, 77, 68, 97, 17, 90, 98, 87, 28, 30, 70, 53, 63, 4, 3, 92, 94, 14, 10, 47, 22, 57, 59, 36, 56, 1, 44, 26, 84, 18, 82, 43, 51, 21, 15, 69, 72, 64, 78, 58, 52, 55, 49, 61, 45, 60, 40, 23, 50, 31, 13, 25, 91, 9, 83, 71, 86, 20, 62, 75, 5, 88, 67, 38, 73, 32, 76, 24, 35, 96, 93, 81, 8, 39, 85, 79, 6, 99, 42, 12, 54, 0, 89, 65, 46, 27, 2, 95, 80, 41, 11, 66, 16, 19, 34]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
1
2

时间复杂度为: O(nlog(n))

当然，也可以用Python自带的内置模块: heapq

import heapq    # q——>queue  优先队列
import random

li = list(range(100))
random.shuffle(li)
print(li)

heapq.heapify(li)  # 建堆
heapq.heappop(li)  # 每次弹出一个最小的元素
print(li)
1
2
3
4
5
6
7
8
9
10

结果为:

[75, 10, 74, 1, 32, 54, 20, 21, 52, 66, 24, 51, 35, 14, 46, 2, 49, 57, 96, 79, 99, 25, 94, 73, 26, 30, 70, 31, 18, 41, 64, 58, 81, 40, 91, 9, 0, 5, 19, 83, 33, 63, 80, 60, 89, 67, 29, 27, 55, 72, 97, 36, 4, 42, 71, 98, 45, 87, 3, 17, 11, 53, 28, 8, 85, 47, 88, 76, 39, 65, 86, 23, 50, 59, 6, 62, 61, 44, 15, 90, 37, 12, 68, 7, 78, 95, 22, 56, 38, 16, 82, 34, 43, 69, 92, 48, 77, 84, 13, 93]
[1, 2, 3, 5, 7, 4, 11, 8, 6, 12, 16, 13, 30, 14, 17, 21, 39, 9, 10, 32, 22, 24, 29, 27, 26, 35, 42, 31, 18, 41, 28, 58, 47, 40, 65, 23, 52, 61, 15, 37, 33, 63, 66, 38, 25, 34, 69, 48, 55, 72, 97, 36, 54, 70, 71, 98, 45, 87, 20, 46, 74, 53, 64, 75, 85, 81, 88, 76, 49, 91, 86, 93, 50, 59, 57, 62, 96, 44, 19, 90, 83, 79, 68, 99, 78, 95, 80, 56, 60, 89, 82, 67, 43, 94, 92, 51, 77, 84, 73]
1
2