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实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Pandas透视表(Pivot Table)的具体使用

《Pandas透视表(PivotTable)的具体使用》透视表用于在数据分析和处理过程中进行数据重塑和汇总,本文就来介绍一下Pandas透视表(PivotTable)的具体使用,感兴趣的可以了解一下... 目录前言什么是透视表?使用步骤1. 引入必要的库2. 读取数据3. 创建透视表4. 查看透视表总结前言

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读