Python 优先队列:heapq库的使用

2024-02-04 09:50

本文主要是介绍Python 优先队列:heapq库的使用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。
🍎个人主页:小嗷犬的个人主页
🍊个人网站:小嗷犬的技术小站
🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。


本文目录

    • 简介
    • heapq 库的使用
      • heapify
      • heappush
      • heappop
      • heapreplace
      • heappushpop
      • merge
      • nlargest
      • nsmallest
    • 例题
      • Title
        • Time Limit
        • Memory Limit
        • Problem Description
        • Input
        • Output
        • Sample Input
        • Sample Onput
        • Note
        • Source
        • Solution


简介

heapq 库是 Python 标准库中的一部分,它提供了一些堆操作的函数,可以用来实现优先队列。

优先队列是一种特殊的队列,它的每个元素都有一个优先级,元素的出队顺序是按照优先级从高到低的顺序进行的。优先队列的实现有多种方式,其中最常用的是堆。

堆是一种特殊的树,有两种类型,分别是最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值,最小堆的每个节点的值都小于或等于其子节点的值。堆的根节点是堆中的最大值(最小堆的根节点是最小值)。

heapq 的大部分操作都是基于最小堆实现的,通过将元素取相反数,可以实现最大堆。


heapq 库的使用

heapq 库提供了 heapifyheappushheappopheapreplaceheappushpopmergenlargestnsmallest 等函数,用于堆的操作。

heapify

heapify 函数用于原地将列表转换为最小堆,时间复杂度为 O ( n ) O(n) O(n)

函数原型如下:

heapq.heapify(x)

其中,x 是一个列表。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
print(x)
# [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

heappush

heappush 函数用于将元素插入到最小堆中,并保持堆的不变性,时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)

函数原型如下:

heapq.heappush(heap, item)

其中,heap 是一个最小堆,item 是要插入的元素。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
heapq.heappush(x, 2.5)
print(x)
# [0, 1, 2, 6, 2.5, 5, 4, 7, 8, 9, 3]

heappop

heappop 函数用于弹出最小堆的根节点,并保持堆的不变性,时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。如果堆为空,则抛出 IndexError 异常。

函数原型如下:

heapq.heappop(heap)

其中,heap 是一个最小堆。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
print(heapq.heappop(x))
# 0
print(x)
# [1, 3, 2, 6, 9, 5, 4, 7, 8]

使用 heap[0] 可以访问最小堆的根节点,但是不会弹出它。

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
print(x[0])
# 0
print(x)
# [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

heapreplace

heapreplace 函数用于弹出最小堆的根节点,并将新元素插入到堆中,保持堆的大小和不变性,时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。如果堆为空,则抛出 IndexError 异常。它比先调用 heappop 再调用 heappush 效率更高。

函数原型如下:

heapq.heapreplace(heap, item)

其中,heap 是一个最小堆,item 是要插入的元素。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
heapq.heapreplace(x, -1)
print(x)
# [-1, 1, 2, 6, 3, 5, 4, 7, 8, 9]

heappushpop

heappushpop 函数用于将元素插入到最小堆中,并弹出最小堆的根节点,保持堆的大小和不变性,时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。如果堆为空,则抛出 IndexError 异常。它比先调用 heappush 再调用 heappop 效率更高。

函数原型如下:

heapq.heappushpop(heap, item)

其中,heap 是一个最小堆,item 是要插入的元素。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(x)
heapq.heappushpop(x, -1)
print(x)
# [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

merge

merge 函数是一个基于堆的通用功能函数,用于合并多个有序的序列,返回一个新的有序的序列,时间复杂度为 O ( n log ⁡ k ) O(n \log k) O(nlogk),其中 n n n 是所有序列的元素个数, k k k 是序列的个数。函数返回一个已排序值的迭代器,可以使用 list 函数将其转换为列表。

函数原型如下:

heapq.merge(*iterables, key=None, reverse=False)

其中,iterables 是多个有序的序列,key 是一个函数,用于从序列中提取比较的键,reverse 是一个布尔值,表示是否反转序列。

示例:

import heapq
x = [1, 3, 5, 7, 9]
y = [2, 4, 6, 8, 10]
z = heapq.merge(x, y)
print(list(z))
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

nlargest

nlargest 函数是一个基于堆的通用功能函数,用于返回最大的 n n n 个元素,时间复杂度为 O ( n log ⁡ k ) O(n \log k) O(nlogk),其中 n n n 是序列的长度, k k k 是要返回的元素个数。如果 n n n 小于 k k k,则返回整个序列。

函数原型如下:

heapq.nlargest(n, iterable, key=None)

其中,n 是要返回的元素个数,iterable 是一个序列,key 是一个函数,用于从序列中提取比较的键。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print(heapq.nlargest(3, x))
# [9, 8, 7]

nlargest 函数在 n n n 值较小时性能较好。对于较大的 n n n,使用 sorted(iterable, reverse=True)[:n] 性能更好。当 n = 1 n=1 n=1 时,使用 max(iterable) 函数性能更好。

nsmallest

nsmallest 函数是一个基于堆的通用功能函数,用于返回最小的 n n n 个元素,时间复杂度为 O ( n log ⁡ k ) O(n \log k) O(nlogk),其中 n n n 是序列的长度, k k k 是要返回的元素个数。如果 n n n 小于 k k k,则返回整个序列。

函数原型如下:

heapq.nsmallest(n, iterable, key=None)

其中,n 是要返回的元素个数,iterable 是一个序列,key 是一个函数,用于从序列中提取比较的键。

示例:

import heapq
x = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print(heapq.nsmallest(3, x))
# [0, 1, 2]

nsmallest 函数在 n n n 值较小时性能较好。对于较大的 n n n,使用 sorted(iterable)[:n] 性能更好。当 n = 1 n=1 n=1 时,使用 min(iterable) 函数性能更好。


例题

Title

CodeForces 1800 C2. Powering the Hero (hard version)

Time Limit

2 seconds

Memory Limit

256 megabytes

Problem Description

This is a hard version of the problem. It differs from the easy one only by constraints on n n n and t t t.

There is a deck of n n n cards, each of which is characterized by its power. There are two types of cards:

You can do the following with the deck:

Your task is to use such actions to gather an army with the maximum possible total power.

Input

The first line of input data contains single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1t104) — the number of test cases in the test.

The first line of each test case contains one integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1n2105) — the number of cards in the deck.

The second line of each test case contains n n n integers s 1 , s 2 , … , s n s_1, s_2, \dots, s_n s1,s2,,sn ( 0 ≤ s i ≤ 1 0 9 0 \le s_i \le 10^9 0si109) — card powers in top-down order.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

Output

Output t t t numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

Sample Input
5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4
Sample Onput
6
6
8
9
4
Note

In the first sample, you can take bonuses 1 1 1 and 2 2 2. Both hero cards will receive 3 3 3 power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero’s card on top of the deck cannot be powered up, and the rest can be powered up with 2 2 2 and 3 3 3 bonuses and get 6 6 6 total power.

In the fourth sample, you can take bonuses 1 1 1, 2 2 2, 3 3 3, 5 5 5 and skip the bonus 6 6 6, then the hero 4 4 4 will be enhanced with a bonus 3 3 3 by 5 5 5, and the hero 7 7 7 with a bonus 5 5 5 by 4 4 4. 4 + 5 = 9 4+5=9 4+5=9.

Source

CodeForces 1800 C2. Powering the Hero (hard version)

Solution

每张英雄牌的最大力量为该英雄牌之前出现的未被使用最大奖励牌的力量。对于具体是哪张英雄牌使用了哪张奖励牌,我们是不关心的,只需要统计他们最大力量即可。

import heapqfor _ in range(int(input())):n = int(input())s = map(int, input().split())h = []ans = 0for i in s:if i == 0 and h:ans -= heapq.heappop(h)else:heapq.heappush(h, -i)print(ans)

这篇关于Python 优先队列:heapq库的使用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677084

相关文章

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Pandas使用SQLite3实战

《Pandas使用SQLite3实战》本文主要介绍了Pandas使用SQLite3实战,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录1 环境准备2 从 SQLite3VlfrWQzgt 读取数据到 DataFrame基础用法:读

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

go中空接口的具体使用

《go中空接口的具体使用》空接口是一种特殊的接口类型,它不包含任何方法,本文主要介绍了go中空接口的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录接口-空接口1. 什么是空接口?2. 如何使用空接口?第一,第二,第三,3. 空接口几个要注意的坑坑1:坑2:坑3:接口-空接口1. 什么是空接

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.