Py008-01-09堆排序

堆排序过程

  • 1.建立堆
  • 2.得到堆顶元素，为最大元素
  • 3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
  • 4.堆顶元素为第二最大元素
  • 5.重复步骤3，直到堆变空

堆向下调整实现

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
# 原地排序，所以 大根堆 堆顶下来的元素会放到列表的末尾
# high则标记 堆的最后一个元素
def sift(li,low,high):
    '''

    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    '''

    i = low # i最开始指向根节点
    j = 2 * i + 1 # j就是i的左孩子
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]: # 如果有右孩子而且 右孩子比左孩子大
            j = j + 1 # 指向右孩子

        if li[j] > tmp: # 要么是左孩子  要么是右孩子
            li[i] = li[j]
            i = j    # 往下看一层
            j = 2 * i + 1

        else: # tmp最大，把tmp放到i的位置上
            li[i] = tmp # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp # 把tmp放到叶子节点上

建立堆

1
2
3
4
5
6
7
8
def heap_sort(li):
    n = len(li)
    # 倒着循环 找村级别
    for i in range((n-2)//2,-1,-1):
        # i表示建堆时候调整的部分的根的下标
        # 此时的high不用 2*i+1
        sift(li,i,n-1)
    # 建堆完成了

挨个出数

  • 因为是原地排序
  • 所以堆顶下台的元素会放到末尾
  • high = 列表长度 - 下太元素的个数
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
# 原地排序，所以 大根堆 堆顶下来的元素会放到列表的末尾
# high则标记 堆的最后一个元素
def sift(li,low,high):
    '''

    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    '''

    i = low # i最开始指向根节点
    j = 2 * i + 1 # j就是i的左孩子
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]: # 如果有右孩子而且 右孩子比左孩子大
            j = j + 1 # 指向右孩子

        if li[j] > tmp: # 要么是左孩子  要么是右孩子
            li[i] = li[j]
            i = j    # 往下看一层
            j = 2 * i + 1

        else: # tmp最大，把tmp放到i的位置上
            li[i] = tmp # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp # 把tmp放到叶子节点上

def heap_sort(li):
    n = len(li)
    # 倒着循环 找村级别
    for i in range((n-2)//2,-1,-1):
        # i表示建堆时候调整的部分的根的下标
        # 此时的high不用 2*i+1
        sift(li,i,n-1)
    # 建堆完成了

    for i in range(n-1,-1,-1):
        # i 指向当前堆的最后一个元素
        # 把堆的最后一个元素放到堆顶
        li[0],li[i] = li[i],li[0]
        # 此时high = i-1 就是前一个元素
        sift(li,0,i-1)

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

heap_sort(li)
print(li)

堆排序的时间复杂度

  • 时间复杂度：O(nlogn)

堆排序——内置模块 heapq

常用函数

  • heapify(x)
  • heappush(heap,item)
  • heappop(heap)
1
2
3
4
5
6
7
8
9
10
11
12
13
import heapq # q=>queue 优先队列
import random

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

heapq.heapify(li) # 建堆

n = len(li)
for i in range(n):
    # 每次出数
    print(heapq.heappop(li),end=',')