" name="sm-site-verification"/>
侧边栏壁纸
博主头像
PySuper博主等级

千里之行,始于足下

  • 累计撰写 203 篇文章
  • 累计创建 14 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

堆排序、Python实现堆排序

PySuper
2021-03-23 / 0 评论 / 0 点赞 / 26 阅读 / 5162 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

堆结构非常重要

优先级列表

把一个数组理解成一个完全二叉树(脑补)

  • 堆结构的heapInsert与heapify
  • 堆结构的增大和减少
  • 如果只是建立堆的过程,时间复杂度为O(N)
  • 优先级队列结构,就是堆结构

二叉树

在不越界的情况下,第 i个元素:

  • 左节点:2 * i + 1
  • 右节点:2 * i + 2
  • 父节点:(i - 1) / 2(0号元素的父节点还是0,-1/2 = 0)

完全二叉树

  • 满二叉树:任何一个非叶节点,一定有左节点和右节点
  • 不是满二叉树:所有节点,从左到右依次补齐

大根堆

任何一棵子树的最大值,都是这棵子树的头部

小根堆

任何一棵子树的最小值,都是这棵子树的头部

生成堆

headInsert

一个新节点加入堆中,同时这个节点向上调整的过程

  • 新进来一个节点,它只可能和H个元素比较:H==>完全二叉树的高度:O(logN)
  • 建立大根堆的过程
    • 时间复杂度:O(N)==> log1 + log2 + log3 …

heapify

堆中有一个值(X)发生变化了,怎么调整才能让这个堆仍然是大根堆

  • 找到X的左节点和右节点,较大的值(M)和X比较
  • 如果X < M:X和M交换

示例

有一个流,不断在吐出数(无序),随时找到流中的中位数

可行方案

  • 方案一
    • 用一个数组装这些数(O(1))
    • 每次需要中位数的时候,对数组排序(O(NlogN))
    • 取出中位数
  • 方案二
    • 使用两个数组(大根堆、小根堆),较小的N/2个都放在大根堆中,较大的N/2都放在小根堆中
    • 当两个数组的长度大于1的时候,从多的数组中,减堆(弹出大根堆/小根堆的堆顶),放到少的数组中
      • 先把第一个和最后一个元素交换(最大值和最小值交换)
      • 然后将heap_size减1(从堆中去掉最大值)
      • 然后经历一遍heapify的过程,继续保持大根堆、小根堆
    • 大根堆和小根堆的堆顶,就是两个数组中的最大值和最小值
    • 一直保持,较小的N/2个在大根堆中,较大的N/2个在小根堆中
    • 这样就可以随时拿到中位数

代码实现

堆排序

时间复杂度O(N*logN)

额外空间复杂度O(1)

  • 把数组通过heap_insert变成大根堆
  • 把最后一个值和堆顶交换
  • 把堆的大小减1 ==> 最大值保持不变的放在了最后一个位置,已经不在堆中了
  • 再从剩下的堆中,做heapify的调整(堆顶被交换成了最小值),又变成了大根堆
  • 再把当前堆中的最后一个值,和堆顶交换
  • … …
注册
class HeapSort:
    def sort(self, arr: list):
        """启动堆排序"""
        if arr is None or len(arr) < 2:
            return

        # 0~i 上形成大根堆
        for i in range(len(arr)):
            self.heap_insert(arr, i)

            # 最后一个数和第一个数交换
        heap_size = len(arr) - 1
        arr[0], arr[heap_size] = arr[heap_size], arr[0]

        # 直到大根堆的长度为0,所有的数就都有序了
        while heap_size > 0:
            self.heapify(arr, 0, heap_size)
            arr[0], arr[heap_size - 1] = arr[heap_size - 1], arr[0]

            # 进过上述操作之后,把heap_size - 1
            heap_size -= 1

        return arr

    def heap_insert(self, arr: list, index: int):
        """在大根堆的基础上添加一个元素,heapInsert使其依然是大根堆"""

        # 这个while是为了能 找到所有的父节点
        while arr[index] > arr[int((index - 1) / 2)]:
            # 只要我比我当前父节点的值大,我就和它完成交换
            arr[index], arr[int((index - 1) / 2)] = arr[int((index - 1) / 2)], arr[index]

            # 同时index向上走
            # 当i走到0的时候,会出现arr[0] = arr[(0-1)/2], while也会停止
            index = int((index - 1) / 2)

    def heapify(self, arr: list, index: int, heap_size: int):
        """heap_size: 已经形成的堆的大小"""
        # 当前元素的左节点
        left = index * 2 + 1

        # 这个while是为了能 找到所有的子节点
        while left < heap_size:

            # 找到左右节点中的 较大值(largest)
            if left + 1 < heap_size and arr[left + 1] > arr[left]:
                # 右节点也不越界,且 右节点>左节点
                largest = left + 1
            else:
                largest = left

            # 我和左右两个节点比较,如果还是我最大,就不用交换
            largest = largest if arr[largest] > arr[index] else index
            if largest == index:
                break
            arr[largest], arr[index] = arr[index], arr[largest]

            index = largest
            left = index * 2 + 1


list_ = [2, 4, 3, 6, 5, 8, 7, 10, 9]
arr = HeapSort().sort(list_)
print(arr)
0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区