IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> Python知识库 -> 【python Tips】那些事半功倍的标准库(3-heapq) -> 正文阅读

[Python知识库]【python Tips】那些事半功倍的标准库(3-heapq)

1. 模块:heapq

1.1 模块方法汇总

__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
           'nlargest', 'nsmallest', 'heappushpop']

"""
heappush: Push item onto heap, maintaining the heap invariant.
heappop: Pop the smallest item off the heap, maintaining the heap invariant.
heapify: ransform list into a heap, in-place, in O(len(x)) time.
heapreplace: Pop and return the current smallest value, and add the new item.
merge: Merge multiple sorted inputs into a single sorted output.
nlargest: Find the n smallest elements in a dataset. Equivalent to:  sorted(iterable, key=key)[:n]
nsmallest: Find the n largest elements in a dataset. Equivalent to:  sorted(iterable, key=key, reverse=True)[:n].
heappushpop: Fast version of a heappush followed by a heappop.
"""

1.2 方法详解和实践

refer: Python标准库模块之heapq
refer: 创建堆

1.2.1 创建堆 heapify

  • 概念:
    创建堆 指的是初始化一个堆实例。在创建 堆 的过程中,我们也可以同时进行 堆化 操作。堆化 就是将一组数据变成 堆 的过程。

  • 创建方法:

    • 使用一个空列表,然后使用heapq.heappush()函数把值加入堆中;
    • 或者使用heap.heapify(list)转换列表成为堆结构
      时间复杂度: O(N)
      空间复杂度: O(N)
  • 语法:heapify(list)

    import heapq
    seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
    heap = []
    for v in seqs:
        heapq.heappush(heap, v)
    print(heap)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]
    
    heapq.heapify(seqs)
    print(seqs)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]
    
    print([heapq.heappop(seqs) for _ in range(len(seqs))])   # out:[2, 3, 4, 5, 7, 11, 12, 34, 65]
    
    import heapq
    # 创建一个空的最小堆
    minHeap = []
    heapq.heapify(minHeap)
    
    # 创建一个空的最大堆
    # 由于Python中并没有内置的函数可以直接创建最大堆,所以一般我们不会直接创建一个空的最大堆。
    
    # 创建带初始值的「堆」, 或者称为「堆化」操作,此时的「堆」为「最小堆」
    heapWithValues = [3,1,2]
    heapq.heapify(heapWithValues)
    
    # 创建最大堆技巧
    # Python中并没有内置的函数可以直接创建最大堆。
    # 但我们可以将[每个元素*-1],再将新元素集进行「堆化」操作。此时,堆顶元素是新的元素集的最小值,也可以转换成原始元素集的最大值。
    # 示例
    maxHeap = [1,2,3]
    maxHeap = [-x for x in maxHeap]
    heapq.heapify(maxHeap)
    # 此时的maxHeap的堆顶元素是-3
    # 将-3转换为原来的元素3,既可获得原来的maxHeap中最大的值是3
    
    

1.2.2 插入元素 heappush

  • 语法:heappush(heap, item)
    # 最小堆插入元素
    heapq.heappush(minHeap, 1)
    # 最大堆插入元素
    # 元素乘以-1的原因是我们将最小堆转换为最大堆。
    heapq.heappush(maxHeap, 1*-1)
    

1.2.3 获取元素

堆获取元素通常指获取堆顶元素

  • 语法:heap[0]

    # 最小堆获取堆顶元素,即最小值
    minHeap[0]
    # 最大堆获取堆顶元素,即最大值
    # 元素乘以 -1 的原因是:我们之前插入元素时,将元素乘以 -1,所以在获取元素时,我们需要乘以 -1还原元素。
    maxHeap[0]*-1
    

1.2.4 删除堆顶元素 heapq.heappop

  • 语法:heapq.heappop(heap)

    # 最小堆删除堆顶元素
    heapq.heappop(seqs)
    # 最大堆删除堆顶元素
    heapq.heappop(seqs)
    

1.2.5 替换堆顶元素 heapq.heaprepalce

  • 语法: heapq.heapify(heap, item)

    import heapq
    
    seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
    heapq.heapify(seqs)
    print(seqs)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]
    heapq.heapreplace(seqs, 200)    
    print(seqs)     # [3, 5, 4, 7, 11, 200, 12, 65, 34]
    
  Python知识库 最新文章
Python中String模块
【Python】 14-CVS文件操作
python的panda库读写文件
使用Nordic的nrf52840实现蓝牙DFU过程
【Python学习记录】numpy数组用法整理
Python学习笔记
python字符串和列表
python如何从txt文件中解析出有效的数据
Python编程从入门到实践自学/3.1-3.2
python变量
上一篇文章      下一篇文章      查看所有文章
加:2021-09-13 09:13:47  更:2021-09-13 09:16:13 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/15 15:03:13-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码