二叉堆

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)