算法——python实现堆排序

文章目录

- - 堆排序
  - - 二叉树
    - 堆
    - 堆排序的过程：
    - 代码实现
    - python中的heapq模块

堆排序

二叉树

关于二叉树的操作，其实核心就是 父节点找子节点，子节点找父节点

如果要将二叉树存储到队列中，就需要找出父子节点之间的规律：

父找子： 2i+1（父与左），2i+2（父与右）
子找父：（i-1）//2

在这里插入图片描述

堆

完全二叉树

在这里插入图片描述

构造堆：从最后一个非叶子节点开始调整

堆排序的过程：

在这里插入图片描述

代码实现

"""
堆排序
""""""
时间复杂度 ：               O(N*logN)
每次调整的时候：要么走左边要么走右边，每次只会走一个树的高度（logN）
"""def sift(li, low, high):"""调整函数，无论是构建堆还是移动堆都需要这个调整函数:param low: 根节点:param high: 堆最后一个元素的位置:return:""""""1. 先把根节点拿出来2. 比较左右节点大小，选择替换3. 将拿出来的根节点放到合适位置"""i = low  # i最开始指向根节点j = 2 * i + 1  # j开始是左孩子tmp = li[low]  # 把堆顶存起来while j <= high:  # 只要j位置有数if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子有并且比较大j = j + 1  # j指向右孩子if li[j] > tmp:li[i] = li[j]i = j  # 往下看一层j = 2 * i + 1else:  # tmp更大，把tmp放到i的位置上li[i] = tmp  # 把tmp放到某一级领导位置上breakelse:li[i] = tmp  # 把tmp放到叶子节点上def heap_sort(li):"""1. 构建大根堆2. 调整堆为完全二叉树3."""n = len(li)for i in range((n - 1 - 1) // 2, -1, -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)  # 将堆空间每次减一，排序li = [i for i in range(100)]
import randomrandom.shuffle(li)
print(li)heap_sort(li)
print(li)

python中的heapq模块

python有一个内置的推排序模块，（在构建堆的时候，构建的是小根堆）

import random
import heapqli = [random.randint(1, 101) for i in range(10)]
print(li)
heapq.heapify(li)  # 建堆（小根堆）
for i in range(len(li)):tmp = heapq.heappop(li)  # 弹出一个最小元素