Python中heapq堆的一些基本操作！！——————Python内置模块heapq（无需安装）

heapq堆

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

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

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

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

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

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

• python的heapq模块提供了对堆的支持。 heapq堆数据结构最重要的特征是heap[0]永远是最小的元素

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