算法——python实现堆排序

堆排序

二叉树

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

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

• 父找子： 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 + 1
        else:  # tmp更大，把tmp放到i的位置上
            li[i] = tmp  # 把tmp放到某一级领导位置上
            break
    else:
        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 random

random.shuffle(li)
print(li)

heap_sort(li)
print(li)

python中的heapq模块

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

import random
import heapq

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

若有错误与不足请指出，关注DPT一起进步吧！！！