欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Python中heapq堆的一些基本操作!!——————Python内置模块heapq(无需安装)

程序员文章站 2022-08-31 09:28:44
heapq堆堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。( heapq库中的堆默认是最小堆)最大堆,二叉树中各个父节点的值总是大于或等于任何一个子节点的值。最小堆,二叉树中各个父节点的值总是小于或等于任何一个子节点的值。我们一般使用二叉堆来实现优先级队列,它的内部调整算法复杂度为logN。堆是一个二叉树,其中最小堆每个父节点的值都小于或等于其所有子节点的值。整个最小堆的最小元素总是位于二叉树的根节点。python的heapq模块提供了对堆的支持。 heap...

heapq堆

  • 堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。( heapq库中的堆默认是最小堆)

  • 最大堆,二叉树中各个父节点的值总是大于或等于任何一个子节点的值。

  • 最小堆,二叉树中各个父节点的值总是小于或等于任何一个子节点的值。

  • 我们一般使用二叉堆来实现优先级队列,它的内部调整算法复杂度为logN。

  • 堆是一个二叉树,其中最小堆每个父节点的值都小于或等于其所有子节点的值。

  • 整个最小堆的最小元素总是位于二叉树的根节点。

  • python的heapq模块提供了对堆的支持。 heapq堆数据结构最重要的特征是heap[0]永远是最小的元素
    Python中heapq堆的一些基本操作!!——————Python内置模块heapq(无需安装)

heapq.heapify(list)

将一个列表转换为heapq堆。

import heapq
ls = [1,3,5,6,7,8,9,10]
heapq.heapify(ls)
print(ls)


[1, 3, 5, 6, 7, 8, 9, 10]

heapq.heappush(heap.item)

在堆中的指定位置添加元素。

import heapq
ls = []
heapq.heappush(ls,4)
print(ls)


[4]

heapq.heappop(heap)

删除并返回最小值,因为堆的特征是heap[0]永远是最小的元素,所以一般都是删除第一个元素。


import heapq
ls = [1,2,5,6,8,9,11,15,20]
heapq.heappop(ls)
print(ls)


2, 6, 5, 15, 8, 9, 11, 20]

heapq.heapreplace(heap,item)

删除最小值,并添加元素。

import heapq
ls = [1,2,5,6,8,9,11,15,20]
heapq.heapreplace(ls,500)
print(ls)


[2, 6, 5, 15, 8, 9, 11, 500, 20]

heapq.merge()

将多个堆合并。

import heapq
ls = [1,2,5,6,8,9,11,15,20]
h = [500,200]
for i in heapq.merge(h,ls):
    print(i,end=' ')


 2 5 6 8 9 11 15 20 500 200

heapq.nlargest(n,heap)

查询堆中的n个最大元素。


import heapq
ls = [1,2,5,6,8,9,11,15,20]
print(heapq.nlargest(3,ls))


[20, 15, 11]

heapq.nsmallest(n,heap)

查询堆中的n个最小元素。

import heapq
ls = [1,2,5,6,8,9,11,15,20]
print(heapq.nsmallest(3,ls))


[1, 2, 5]

本文地址:https://blog.csdn.net/Kinght_123/article/details/111995989

相关标签: Python 笔记