python标准库--heapq堆队列算法
发布日期:2021-05-07 21:56:24 浏览次数:18 分类:精选文章

本文共 729 字,大约阅读时间需要 2 分钟。

Python 提供了 heapq 模块来实现堆队列(又称优先队列)算法。这个模块最常用的操作包括以下三个方法:

  • heapq.heappush(heap, item):将 item 的值加入 heap 中,同时保持堆的不变性。需要注意的是,item 可以是元组类型,这样可以为存储多个属性值提供支持,堆会根据元组的第一个元素进行比较。

  • heapq.heappop(heap):弹出并返回 heap 中的最小元素,同时保持堆的不变性。如果堆为空,会抛出 IndexError 异常。用户也可以通过 heap[0] 来直接访问最小的元素,而无需弹出它。

  • heapq.heapify(x):将 list x 转换为堆,操作完成后,原地进行,时间复杂度为 O(n)。

  • 以下是一个示例:

    import heapqif __name__ == '__main__':    # 初始化一个空堆    h = []        # 将元素按顺序加入堆中    heapq.heappush(h, (4, "a"))    heapq.heappush(h, (2, "b"))    heapq.heappush(h, (4, "c"))        # 查看并弹出堆中的最小元素    while h:        print(heapq.heappop(h))        # 将现有列表转换为堆    h = [10, 6, 8, 3, 4, 1, 2, 7, 9, 5]    heapq.heapify(h)    print(h)

    这个代码示例展示了如何使用 heapq 模块来创建和操作堆结构。通过合理使用这些方法,开发者可以轻松实现堆队列的常见功能。

    上一篇:767 重构字符串(大根堆--贪心)
    下一篇:1335 工作计划的最低难度(动态规划)

    发表评论

    最新留言

    哈哈,博客排版真的漂亮呢~
    [***.90.31.176]2025年05月09日 14时56分37秒