当前位置:   article > 正文

Python中的模块heapq以及使用方法详解_python heapq

python heapq

python中的 heapq 模块

1、heapq 的两个函数:nlargest() 和 nsmallest()

1.1 nlargest(n, iterable, key=None) 函数

功能:获取可迭代对象iterable中n个最大的元素,返回这n个最大的元素列表(该列表从最大到小排列)

  • 示例代码1:
import heapq

arr_list = [5, 595, 2, 19, 5, 68, 4, 165, 46, 16]
print(heapq.nlargest(3, arr_list))

# 打印结果 [595, 165, 68]
# 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
'
运行
  • 示例代码2(参数key的用法):
"""
    key 的用法是,对于这种列表套字典的数据,根据字典的某个键,取出该数据的n个这个键的最大的n个数据
"""
import heapq

data_list = [
    {"name": "python", "price": 90},
    {"name": "java", "price": 34},
    {"name": "c", "price": 60},
    {"name": "html", "price": 70},
    {"name": "go", "price": 83}
]

price_max_3 = heapq.nlargest(3, data_list, key=lambda x: x['price'])
print(price_max_3)

# 打印结果 [{'name': 'python', 'price': 90}, {'name': 'go', 'price': 83}, {'name': 'html', 'price': 70}]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
'
运行

1.2 nsmallest(n, iterable, key=None) 函数

功能:获取可迭代对象iterable中n个最小的元素,返回这n个最小的元素列表(该列表从最小到大排列)

  • 示例代码1:
import heapq

arr_list = [5, 595, 2, 19, 5, 68, 4, 165, 46, 16]
print(heapq.nsmallest(3, arr_list))

# 打印结果 [2, 4, 5]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
'
运行
  • 示例代码2(参数key的用法):
"""
    key 的用法是,对于这种列表套字典的数据,根据字典的某个键,取出该数据的n个这个键的最小的n个数据
"""
import heapq

data_list = [
    {"name": "python", "price": 90},
    {"name": "java", "price": 34},
    {"name": "c", "price": 60},
    {"name": "html", "price": 70},
    {"name": "go", "price": 83}
]

# price_max_3 = heapq.nlargest(3, data_list, key=lambda x: x['price'])
price_min_3 = heapq.nsmallest(3, data_list, key=lambda x: x['price'])
print(price_min_3)

# 打印结果 [{'name': 'java', 'price': 34}, {'name': 'c', 'price': 60}, {'name': 'html', 'price': 70}]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
'
运行

2、heapq 的 heapify()函数

heapify() 函数将普通的列表转换为堆

heapify() 函数通过将普通列表转换为堆,使得我们可以使用堆中提供的一些高效的操作,
例如 heappush()、heappop()、heapreplace() 等函数,
这些函数能够在常数时间内插入元素、弹出最小元素、替换最小元素。
这使得堆成为一种非常高效的数据结构,在诸多算法中得以广泛应用。

heapify() 函数将普通的列表转换为堆的过程如下:
1、从列表的末尾开始,依次向前遍历所有元素。对于每个元素,将其与它的父节点进行比较。如果该元素比其父节点小(或大,如果是大根堆),则将它与其父节点交换。
2、继续向前遍历,对于每个元素,重复上述比较和交换过程,直至整个列表变成一个堆。
3、最终得到的堆中,第一个元素是堆中最小的元素(或最大的元素,如果是大根堆)。


大根堆和小根堆是堆(Heap)这种数据结构的两种常见实现方式。它们的区别如下:
    大根堆:在大根堆中,每个节点的值都大于等于其子节点的值,堆中最大的元素位于堆的根节点。
    小根堆:在小根堆中,每个节点的值都小于等于其子节点的值,堆中最小的元素位于堆的根节点。
在一般的堆排序算法中,都使用小根堆来实现堆。这是因为小根堆的根节点是堆中最小的元素,可以方便地弹出并加入一个序列,从而完成排序。当然,如果需要寻找序列中最大的元素,也可以使用大根堆实现。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 示例代码:
import heapq

arr_list = [5, 595, 2, 19, 5, 68, 4, 165, -20, 46, 16]
heapq.heapify(arr_list)  # 默认是转化为小根堆
print("默认的小根堆:", arr_list)
arr_list = [-x for x in arr_list]  # 取相反数,转换为大根堆
heapq.heapify(arr_list)  # 转换为大根堆
arr_list = [-x for x in arr_list]
print("取反后的大根堆:", arr_list)

# 打印结果
# 默认的小根堆: [-20, 5, 2, 19, 5, 68, 4, 165, 595, 46, 16]
# 取反后的大根堆: [595, 165, 68, 19, 46, 2, 4, 5, -20, 5, 16]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
'
运行

2、heapq 的 heappop()函数

将第一个元素(最小的)弹出,然后以第二小的元素取而代之,复杂度为O(logN), N代表堆的大小

import heapq

arr_list = [5, 595, 2, 19, 5, 68, 4, 165, -20, 46, 16]
heapq.heapify(arr_list)  # 默认是转化为小根堆
print(heapq.heappop(arr_list))  # -20
print(heapq.heappop(arr_list))  # 2
print(heapq.heappop(arr_list))  # 4
print(heapq.heappop(arr_list))  # 5
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
'
运行

3. heapq 的 heappush()函数

heapq.heappush(heap, item)

用于将一个元素添加到一个堆中,并保持堆的不变性。
这个函数接受两个参数:
    heap:表示要添加元素的堆。堆可以是一个列表,也可以是一个支持类似于列表的接口的对象。
    item:要添加的元素。
heappush() 函数将要添加的元素插入堆中,并保持堆的不变性。插入的元素必须是可比较的对象,因为堆中的元素必须可以进行排序。默认情况下,heappush() 函数会按照元素的大小进行排序,因此通常要求元素是数字类型或实现了比较操作的自定义对象。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 示例代码:
import heapq

# 创建一个空堆
heap = []

# 添加一些元素到堆中
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

# 查看堆中的元素
print(heap)

# 打印结果
# [1, 1, 4, 3]
# 使用 heappush() 函数向一个空堆 heap 中添加了四个元素。
# 由于 heappush() 函数会按照元素的大小进行排序,因此添加的元素在堆中被自动排序了。
# 最后,我们打印出堆中的元素,结果为 [1, 1, 4, 3]。可以看到,堆中的元素已经按照升序排列,
# 并且包含了多个相同元素。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
'
运行

4. 使用 heapq 模块实现一个简单的优先级队列

import heapq


class PriorityQueue:
    """
        heapq 模块实现的简单的优先级队列
    """

    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        # 把 priority 取负值是未来让队列能够按元素的优先级从高到低的顺序排列
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


class Item:

    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return "Item({!r})".format(self.name)


q = PriorityQueue()
# 往队列里面推数据
q.push(Item(name='python'), 5)  # 设置name为python,优先级为1
q.push(Item(name='java'), 1)  # 设置name为python,优先级为1
q.push(Item(name='c'), 1)  # 设置name为python,优先级为1
q.push(Item(name='vue'), 3)  # 设置name为python,优先级为1
q.push(Item(name='go'), 2)  # 设置name为python,优先级为1

# 从队列里面取出数据,按照设置的优先级,取出数据
print(q.pop())  # Item('python')
print(q.pop())  # Item('vue')
print(q.pop())  # Item('go')
print(q.pop())  # Item('java')
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
'
运行
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/1020043
推荐阅读
相关标签
  

闽ICP备14008679号