Python3，手写一个堆 及其 简易功能，并实现优先队列，最小堆任务调度等

于 2021-08-04 10:48:04 发布
阅读量791 收藏 2
点赞数
分类专栏： 基础算法题练习 文章标签： python 数据结构 堆排序
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/pythonstrat/article/details/119378788
版权

大家可以查看我这篇文章中对堆和堆排序的描述：

下面是简单实现的堆

  • 实现了四种方法：
  • （1）heapify： 将数组调整为堆
  • （2）heappop: 删除堆顶元素
  • （3）heappush：向堆中添加元素
  • （4）heapSort: 堆排序
  • （5） 另外我实现的是大根堆，官网是小根堆，且下标都是从0开始。

大根堆代码展示：

class Heapq:
    """
        生成大根堆
    """

    def __HeapAdjust(self, nums: list, start: int, end: int) -> None:
        """
            筛选法调整堆：
            堆是以列表进行表示的, 假设 [start + 1, end] 已经是堆了，要把[start, end] 变为堆
        """
        i = start
        # 记录一下堆顶元素（这是要调整到堆里的元素）
        rc = nums[i]
        # 判断不能超过堆长度（也就是此刻数组的长度）
        while i * 2 + 1 <= end:
            # 左子节点
            j = i * 2 + 1
            # 判断左右子节点哪个大, nums[j] < end 说明存在右子节点
            if j < end and nums[j] < nums[j + 1]: j += 1
            # 将 rc 与 最大的子节点比较, 如果大于等于当前子节点，说明该插入到这
            if rc >= nums[j]: break
            # 否则，子节点上移
            nums[i] = nums[j]
            i = j
        
        # 最后不管是找到插入位置，还是执行到最后到了叶子结点，都是插入位置
        nums[i] = rc

    
    def __heapify(self, nums: list) -> None:
        """
            将数组变为堆， 由完全二叉树的性质可知，（下标从1开始）所有下标大于 n // 2 的节点都是叶子结点，
            而 叶子结点都是以自己为 根的堆。 我们只需要 将 前 0 - n // 2的 节点进行 调整堆，就可以把整个列表调整为堆
        """
        n = len(nums)
        for i in range((n + 1) // 2 - 1, -1, -1):
            # 调用调整堆函数
            self.__HeapAdjust(nums, i ,n - 1)
    
    
    def __pop(self, nums: list) -> int:
        """
            删除堆中最大的元素，堆顶元素
        """
        n = len(nums)
        nums[0], nums[-1] = nums[-1], nums[0]
        # 得到最大值，堆顶元素，然后调整堆
        rst = nums.pop()
        # 元素大于0时才能执行调整堆
        # 2022.1.4 这里好像应该是 大于 1
        if len(nums) > 0:
            self.__HeapAdjust(nums, 0 ,n - 2)

        return rst


    def __push(self, nums: list, num: int):
        """
            向堆中添加元素， 因为是列表，默认尾部添加
        """
        nums.append(num)
        # 此时 num 为叶子节点，应该由下到上找到他该插入的位置
        n = len(nums)
        i = n - 1
        # 寻找位置不能超过列表上限（堆顶）
        while (i - 1) // 2 >= 0:    
            """
                这里说明一下，因为以 0 为开始节点的情况下， 根 左右三者关系是 i i * 2 + 1   i * 2 + 2
                无法从叶子结点 // 2 得到根节点。  但是以 1为开始的就可以。 i  i*2, i * 2 + 1  
            """
            cur_root = (i - 1) // 2
            # 小于当前根节点，那就插入到当前位置
            if nums[cur_root] > num: break
            nums[i] = nums[cur_root]
            i = cur_root

        # 最后到了，为根位置了，或者找到插入位置，都执行插入
        nums[i] = num
    

    # 对外提供的接口
    def heapify(self, nums: list) -> None:
        """
            把数组调整为大根堆
        """
        self.__heapify(nums)
    

    def heappop(self, nums: list) -> int:
        """
            删除堆顶元素并返回
        """
        return self.__pop(nums)


    def heappush(self, nums: list, num: list) -> None:
        """
            向堆内添加元素
        """
        self.__push(nums, num)

    
    def heapSort(self, nums: list) -> None:
        """
            :param      nums: int
            将普通数组通过堆排序并返回, 原地排序，不适用额外数组
        """
        n = len(nums)
        # 先建堆
        self.__heapify(nums)
        # 再进行堆排序
        for i in range(n-1, 0, -1):
            # 将堆顶元素交换到堆尾，再进行调整堆
            nums[0], nums[i] = nums[i], nums[0]
            # 调整堆，将 [0, i - 1] 调整为堆
            self.__HeapAdjust(nums, 0, i - 1)

    def heapSort1(self, nums: list) -> None:
        """
            利用 heappop实现排序，测试 heappop()功能。 排序效率肯定是不如上面交换的
        """
        n = len(nums)
        # 先建堆
        self.__heapify(nums)
        # 再进行堆排序
        sortL = list()
        for i in range(n):
            rst = self.heappop(nums)
            sortL.append(rst)
        
        return sortL


# 开始测试

nums = [49, 38, 65, 97, 76, 13, 27, 49]
heap = Heapq()
# 1. 创建堆，并进行堆排序
# heap.heapSort(nums)
# heap.heapify(nums)

# 2. 测试pop()
# rst = heap.heappop(nums)

# 3. 测试 push()
heapList = []
for num in nums:
    heap.heappush(heapList, num)

# 此时heapList已经是堆了
print(heapList)
rst = heap.heapSort1(heapList)

print(heapList)
print(rst)

"""
heapList    [97, 76, 49, 49, 65, 13, 27, 38]
下标          0   1   2   3   4   5   6    7
堆：
                          97
                    76         49
                49     65   13    27 
            38

"""

小根堆代码：和大根堆一样

class Heapq:
    """
        生成小根堆，和大根堆是一样的
    """

    def __HeapAdjust(self, nums: list, start: int, end: int) -> None:
        i = start
        rc = nums[i]
        while i * 2 + 1 <= end:
            j = i * 2 + 1
            if j < end and nums[j] > nums[j + 1]: j += 1
            if rc <= nums[j]: break
            nums[i] = nums[j]
            i = j
        
        nums[i] = rc

    
    def __heapify(self, nums: list) -> None:
        n = len(nums)
        for i in range((n + 1) // 2 - 1, -1, -1):
            self.__HeapAdjust(nums, i ,n - 1)
    
    
    def __pop(self, nums: list) -> int:
        n = len(nums)
        nums[0], nums[-1] = nums[-1], nums[0]
        rst = nums.pop()
        if len(nums) > 0:
            self.__HeapAdjust(nums, 0 ,n - 2)

        return rst


    def __push(self, nums: list, num: int):
        nums.append(num)
        n = len(nums)
        i = n - 1
        while (i - 1) // 2 >= 0: 
            cur_root = (i - 1) // 2
            if nums[cur_root] < num: break
            nums[i] = nums[cur_root]
            i = cur_root

        nums[i] = num
    

    # 对外提供的接口
    def heapify(self, nums: list) -> None:
        """
            把数组调整为大根堆
        """
        self.__heapify(nums)
    

    def heappop(self, nums: list) -> int:
        """
            删除堆顶元素并返回
        """
        return self.__pop(nums)


    def heappush(self, nums: list, num: list) -> None:
        """
            向堆内添加元素
        """
        self.__push(nums, num)

    
    def heapSort(self, nums: list) -> None:
        """
            :param      nums: int
            将普通数组通过堆排序并返回, 原地排序，不适用额外数组
        """
        n = len(nums)
        self.__heapify(nums)
        for i in range(n-1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            self.__HeapAdjust(nums, 0, i - 1)

（1）第一个场景，排序。

  • 根据慕课专栏：Python 源码深度剖析/16 最佳实践：灵活运用内建容器，提高开发效率
  • 场景： 假设王者荣耀这款游戏要出一个排行榜， 统计段位最高的前100名玩家。
  • 分析： 因为王者荣耀用户人数众多，如果使用普通的排序，例如快速排序，那么时间复杂度将高达O（NlogN）,当N计数很大时，计算开销也跟着增大！ 并且，我们只需要统计前100名玩家的顺序， 并不需要全部排列，也就是不关心后面玩家的名次。
  • 那么就可以使用最小堆来解决：

（引入专栏源码）

from heapq import heappush, heappop

# 用一个最小堆来保存积分最多的100位用户
# 这样，积分最小的用户刚好在堆顶
top100 = []

# 遍历所有用户
for user in users:
    # 堆未满100，不断压入
    if len(top100) < 100:
        heappush(top100, user)
        continue
        
    # 如果当前用户积分比堆中积分最少的用户多，则替换
    if user > top100[0]:
        heappop(top100)
        heappush(top100, user)
        
 # 遍历完毕后，现在堆中保存的用户就是积分最多的100位了

  • 引入最小堆后，制作排行榜的时间复杂度降为 O(Nlog100)。由于 O(Nlog100)O(Nlog100)是个常数，因此时间复杂度等价于O(N)O(N)更一般地，假设为NN位用户制作长度为KK的排行榜，两个方案的的时间复杂度分别是：

    全量排序：O(NlogN)O(NlogN)；
    最小堆：O(NlogK)O(NlogK)；
    由于一般情况下，K 远小于，N因此采用最小堆性能更理想！

（2）基于最小堆的任务调度系统

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值