Python常用数据结构之heapq模块建议收藏

heapq堆是一种特殊的树形结构,通常我们所说的堆的数据结构指的是完全二叉树,并且根节点的值小于等于该节点所有子节点的值常用方法常用方法示例>>>[15,2,50,3

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Python常用数据结构之heapq模块建议收藏此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

Python数据结构常用模块collections、heapq、operator、itertools

heapq

  堆是一种特殊的树形结构,通常我们所说的堆的数据结构指的是完全二叉树,并且根节点的值小于等于该节点所有子节点的值

                                                       Python常用数据结构之heapq模块建议收藏

常用方法

heappush(heap,item) 往堆中插入一条新的值
heappop(heap) 从堆中弹出最小值
heapreplace(heap,item) 从堆中弹出最小值,并往堆中插入item
heappushpop(heap,item) Python3中的heappushpop更高级
heapify(x) 以线性时间将一个列表转化为堆
merge(*iterables,key=None,reverse=False) 合并对个堆,然后输出
nlargest(n,iterable,key=None) 返回可枚举对象中的n个最大值并返回一个结果集list
nsmallest(n,iterable,key=None) 返回可枚举对象中的n个最小值并返回一个结果集list

常用方法示例 

#coding=utf-8

import heapq
import random

def test():
    li = list(random.sample(range(100),6))
    print (li)

    n = len(li)
    #nlargest
    print ("nlargest:",heapq.nlargest(n, li))
    #nsmallest
    print ("nsmallest:", heapq.nsmallest(n, li)) 
    #heapify
    print('original list is', li) 
    heapq.heapify(li) 
    print('heapify  list is', li)  
    # heappush & heappop  
    heapq.heappush(li, 105)  
    print('pushed heap is', li)  
    heapq.heappop(li)  
    print('popped heap is', li)  
    # heappushpop & heapreplace  
    heapq.heappushpop(li, 130)    # heappush -> heappop  
    print('heappushpop', li)  
    heapq.heapreplace(li, 2)    # heappop -> heappush  
    print('heapreplace', li) 

  >>> [15, 2, 50, 34, 37, 55]
  >>> nlargest: [55, 50, 37, 34, 15, 2]
  >>> nsmallest: [2, 15, 34, 37, 50, 55]
  >>> original list is [15, 2, 50, 34, 37, 55]
  >>> heapify  list is [2, 15, 50, 34, 37, 55]
  >>> pushed heap is [2, 15, 50, 34, 37, 55, 105]
  >>> popped heap is [15, 34, 50, 105, 37, 55]
  >>> heappushpop [34, 37, 50, 105, 130, 55]
  >>> heapreplace [2, 37, 50, 105, 130, 55]

堆排序示例 

  heapq模块中有几张方法进行排序:

  方法一:

#coding=utf-8

import heapq

def heapsort(iterable):
    heap = []
    for i in iterable:
        heapq.heappush(heap, i)

    return [heapq.heappop(heap) for j in range(len(heap))]
        
if __name__ == "__main__":
    li = [30,40,60,10,20,50]
    print(heapsort(li))

  >>>> [10, 20, 30, 40, 50, 60]

  方法二(使用nlargest或nsmallest):

li = [30,40,60,10,20,50]
#nlargest
n = len(li)
print ("nlargest:",heapq.nlargest(n, li))
#nsmallest
print ("nsmallest:", heapq.nsmallest(n, li))

  >>> nlargest: [60, 50, 40, 30, 20, 10]
  >>> nsmallest: [10, 20, 30, 40, 50, 60]

  方法三(使用heapify):

def heapsort(list):
    heapq.heapify(list)
    heap = []

    while(list):
        heap.append(heapq.heappop(list))
        
    li[:] = heap
    print (li)
        
if __name__ == "__main__":
    li = [30,40,60,10,20,50]
    heapsort(li)

  >>> [10, 20, 30, 40, 50, 60]

堆在优先级队列中的应用

  需求:实现任务的添加,删除(相当于任务的执行),修改任务优先级

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

 

  

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120201.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • python pandas fillna_python rfind函数

    python pandas fillna_python rfind函数本文概述我们可以使用fillna()函数填充数据集中的空值。句法DataFrame.fillna(value=None,method=None,axis=None,inplace=False,limit=None,downcast=None,**kwargs)参数值:它是一个用于填充空值的值,或者是一个Series/dict/DataFrame。method:一种用于填充重新…

  • 深圳易速马网络科技有限公司_动易网络

    深圳易速马网络科技有限公司_动易网络纵观现如今国内CMS程序,大有百花争艳的感觉,随着企业建站需求的复杂度和功能的不断扩展,传统的三五个人写一段代码即告网站建已经行不通,于是以内容管理为应用核心的CMS产品大行其道。  这些CMS系统大体上基于两套框架编写:PHP+MySQL和.NET+MSSQL。在PHP中比较有名的就有DeDeCMS、PHP168、帝国CMS、Supesite等,在.NET方面就有zoomla!CMS、

  • 网上书城项目-LoadRunner压力测试

    网上书城项目-LoadRunner压力测试1.LoadRunner12.02安装教程及中文语言包安装2.如何使用loadrunner进行web网站性能测试3.解决loadrunner12版本中不显示监控图表的问题

  • 创建xsync 脚本

    创建xsync 脚本1、安装rsync:yum-yinstallrsync2、创建xsync文件并进行编辑(最好放到配置过环境变量的目录下)输入命令:vi/usr/local/spark/spark-standalone/bin/xsync#!/bin/bash#1获取输入参数个数,如果没有参数,直接退出pcount=$#if[$pcount-lt1]thenechoNoEnoughArguement!exit;fi#2.遍历集群所有机器forh…

  • 【SpringBoot】45、SpringBoot中整合JWT实现Token验证(注解篇)「建议收藏」

    前言上篇文章,我们已经在SpringBoot中整合了JWT并实现了Token验证,那我们在实际应用中就会发现,如果每个视图层(controller)都手动验证token,代码就会显得特别臃肿,本篇文章主要为了解决该问题。如果对整合JWT还不熟悉的朋友,可以先看看我的这篇博客:【SpringBoot】四十四、SpringBoot中整合JWT实现Token验证自定义注解1、创建自定义注解packagecom.asurplus.common.annotation;import

  • 微信小程序页面跳转 回退页面api

    微信小程序页面跳转 回退页面api小程序如果 跳转url后 需要直接返回首页或者回退之前好几个页面,跳转url时用 wx.redirectTo设置好回退的参数即可。如果返回上一页时 跳转url时用 wx.navigateTo

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号