数据结构-堆

目录

heapq

导入

初始化 

插入元素

返回最小值

PriorityQueue

导入

初始化

入队

出队

---

堆是一颗树，其每个节点都有一个值，且（小根堆：每个父节点都小于等于其子节点

（在进树时不断进行比较

STL中的 priority_queue 其实就是一个大根堆

python中可以用 heapq（小根堆） 和 PriorityQueue （大根堆）

heapq

heapq默认是小根堆，如果想实现大根堆的话得负负得正

导入

import heapq

初始化 

heap=[]

或者从列表转化而来

heapq.heapify(列表名)

那么后面堆名就是列表名

插入元素

heapq.heappush(堆名，插入元素值)

返回最小值

heapq.heappop(堆名)

PriorityQueue

在这PQ里我们需要自己设置优先级，一般情况下就是元素值等于优先级值

从不是标准库的deque导入

注意⚠️：PriorityQueue得从不是标准库的deque导入

from deque import PriorityQueue

初始化

pq=PriorityQueue()

入队

pq.put([优先级，元素值])

出队

取出优先级最高的（小根堆的话也是负负得正

pq.get()