二叉堆
import heapq
lst = [3, 1, 7, 9, 5]
# 无论是插入还是删除，在进行操作之前必须调用heapify方法建堆。
heapq.heapify(lst)
# 插入
heapq.heappush(lst, 6)
# 取出最小元素
while len(lst) != 0:
print(heapq.heappop(lst))
# 前2小元素
max_v = heapq.nlargest(2, lst)
min_v = heapq.nsmallest(2, lst)
heapify(包括heapq封装的其他操作)都不会更改数据结构(仍为list)，只会以堆的操作规范对其进行处理。
LRU 算法
class Node:
def __init__(self, k: int, v: int):
self.key = k
self.val = v
self.next = None
self.prev = None
class DoubleList:
# 头尾虚节点
def __init__(self):
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
# 在链表尾部添加节点 x，时间 O(1)
def addLast(self, x: Node):
x.prev = self.tail.prev
x.next = self.tail
self.tail.prev.next = x
self.tail.prev = x
self.size += 1
# 删除链表中的 x 节点（x 一定存在）
# 由于是双链表且给的是目标 Node 节点，时间 O(1)
def remove(self, x: Node):
x.prev.next = x.next
x.next.prev = x.prev
self.size -= 1
# 删除链表中第一个节点，并返回该节点，时间 O(1)
def removeFirst(self) -> Node:
if self.head.next == self.tail:
return None
first = self.head.next
self.remove(first)
return first
# 返回链表长度，时间 O(1)
def size(self) -> int:
return self.size
class LRUCache:
def __init__(self, capacity: int):
# key -> Node(key, val)
self.map = {}
# Node(k1, v1) <-> Node(k2, v2)...
self.cache = DoubleList()
# 最大容量
self.cap = capacity
# 将某个 key 提升为最近使用的
def makeRecently(self, key: int):
x = self.map[key]
# 先从链表中删除这个节点
self.cache.remove(x)
# 重新插到队尾
self.cache.addLast(x)
# 添加最近使用的元素
def addRecently(self, key: int, val: int):
x = Node(key, val)
# 链表尾部就是最近使用的元素
self.cache.addLast(x)
# 别忘了在 map 中添加 key 的映射
self.map[key] = x
# 删除某一个 key
def deleteKey(self, key: int):
x = self.map[key]
# 从链表中删除
self.cache.remove(x)
# 从 map 中删除
self.map.pop(key)
# 删除最久未使用的元素
def removeLeastRecently(self):
# 链表头部的第一个元素就是最久未使用的
deletedNode = self.cache.removeFirst()
# 同时别忘了从 map 中删除它的 key
deletedKey = deletedNode.key
self.map.pop(deletedKey)
def get(self, key: int) -> int:
if key not in self.map:
return -1
# 将该数据提升为最近使用的
self.makeRecently(key)
return self.map[key].val
def put(self, key: int, val: int) -> None:
if key in self.map:
# 删除旧的数据
self.deleteKey(key)
# 新插入的数据为最近使用的数据
self.addRecently(key, val)
return
if self.cap == self.cache.size():
# 删除最久未使用的元素
self.removeLeastRecently()
# 添加为最近使用的元素
self.addRecently(key, val)
