❌

阅读视图

发现新文章，点击刷新页面。

懒删除堆（Python/Java/C++/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

为了实现 $\texttt{execTop}$，用最大堆维护优先级、任务编号、用户编号。

为了实现堆的懒更新和懒删除，用一个哈希表记录每个任务编号对应的最新的优先级和用户编号。哈希表的 key 是任务编号，value 是优先级和用户编号组成的二元组。

  • $\texttt{edit}$：直接把一个新的优先级、任务编号、用户编号三元组入堆。同时更新哈希表。
  • $\texttt{rmv}$：把元素从哈希表中删掉。更简单的写法是，把优先级改成 $-1$。
  • $\texttt{execTop}$：不断弹出「货不对板」的堆顶，也就是任务编号和哈希表中记录的数据不一致的堆顶。直到堆为空或者找到一致的数据。

注 1：如果你学过 Dijkstra 算法，其中的堆就是懒更新堆。

注 2：题目保证输入的 $\textit{tasks}$ 数组中没有重复的 $\textit{taskId}$。

###py

class TaskManager:
    def __init__(self, tasks: List[List[int]]):
        self.mp = {taskId: (priority, userId) for userId, taskId, priority in tasks}
        self.h = [(-priority, -taskId, userId) for userId, taskId, priority in tasks]  # 取相反数，变成最大堆
        heapify(self.h)

    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.mp[taskId] = (priority, userId)
        heappush(self.h, (-priority, -taskId, userId))

    def edit(self, taskId: int, newPriority: int) -> None:
        # 懒修改
        self.add(self.mp[taskId][1], taskId, newPriority)

    def rmv(self, taskId: int) -> None:
        # 懒删除
        self.mp[taskId] = (-1, -1)

    def execTop(self) -> int:
        while self.h:
            priority, taskId, userId = heappop(self.h)
            if self.mp[-taskId] == (-priority, userId):
                self.rmv(-taskId)
                return userId
            # else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        return -1

###java

class TaskManager {
    // taskId -> (priority, userId)
    private final Map<Integer, int[]> mp = new HashMap<>();

    // (priority, taskId, userId)
    private final PriorityQueue<int[]> pq =
            new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);

    public TaskManager(List<List<Integer>> tasks) {
        for (List<Integer> task : tasks) {
            add(task.get(0), task.get(1), task.get(2));
        }
    }

    public void add(int userId, int taskId, int priority) {
        mp.put(taskId, new int[]{priority, userId});
        pq.offer(new int[]{priority, taskId, userId});
    }

    public void edit(int taskId, int newPriority) {
        // 懒修改
        int userId = mp.get(taskId)[1];
        add(userId, taskId, newPriority);
    }

    public void rmv(int taskId) {
        // 懒删除
        mp.get(taskId)[0] = -1;
    }

    public int execTop() {
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int priority = top[0], taskId = top[1], userId = top[2];
            int[] p = mp.get(taskId);
            if (p[0] == priority && p[1] == userId) {
                rmv(taskId);
                return userId;
            }
            // else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        }
        return -1;
    }
}

###cpp

class TaskManager {
    unordered_map<int, pair<int, int>> mp; // taskId -> (priority, userId)
    priority_queue<tuple<int, int, int>> pq; // (priority, taskId, userId)

public:
    TaskManager(vector<vector<int>>& tasks) {
        for (auto& task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }

    void add(int userId, int taskId, int priority) {
        mp[taskId] = {priority, userId};
        pq.emplace(priority, taskId, userId);
    }

    void edit(int taskId, int newPriority) {
        // 懒修改
        add(mp[taskId].second, taskId, newPriority);
    }

    void rmv(int taskId) {
        // 懒删除
        mp[taskId].first = -1;
    }

    int execTop() {
        while (!pq.empty()) {
            auto [priority, taskId, userId] = pq.top();
            pq.pop();
            if (mp[taskId] == pair(priority, userId)) {
                rmv(taskId);
                return userId;
            }
            // else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        }
        return -1;
    }
};

###go

type pair struct{ priority, userId int }

type TaskManager struct {
mp map[int]pair // taskId -> (priority, userId)
h  *hp          // (priority, taskId, userId)
}

func Constructor(tasks [][]int) TaskManager {
n := len(tasks)
mp := make(map[int]pair, n) // 预分配空间
h := make(hp, n)
for i, t := range tasks {
userId, taskId, priority := t[0], t[1], t[2]
mp[taskId] = pair{priority, userId}
h[i] = tuple{priority, taskId, userId}
}
heap.Init(&h)
return TaskManager{mp, &h}
}

func (t *TaskManager) Add(userId, taskId, priority int) {
t.mp[taskId] = pair{priority, userId}
heap.Push(t.h, tuple{priority, taskId, userId})
}

func (t *TaskManager) Edit(taskId, newPriority int) {
// 懒修改
t.Add(t.mp[taskId].userId, taskId, newPriority)
}

func (t *TaskManager) Rmv(taskId int) {
// 懒删除
t.mp[taskId] = pair{-1, -1}
}

func (t *TaskManager) ExecTop() int {
for t.h.Len() > 0 {
top := heap.Pop(t.h).(tuple)
priority, taskId, userId := top.priority, top.taskId, top.userId
if t.mp[taskId] == (pair{priority, userId}) {
t.Rmv(taskId)
return userId
}
// else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
}
return -1
}

type tuple struct{ priority, taskId, userId int }
type hp []tuple
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return cmp.Or(h[i].priority-h[j].priority, h[i].taskId-h[j].taskId) > 0 }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

###js

class TaskManager {
    constructor(tasks) {
        // taskId -> [priority, userId]
        this.mp = new Map();

        // 最大堆 [priority, taskId, userId]
        this.pq = new PriorityQueue((a, b) => a[0] !== b[0] ? b[0] - a[0] : b[1] - a[1]);

        for (const [userId, taskId, priority] of tasks) {
            this.add(userId, taskId, priority);
        }
    }

    add(userId, taskId, priority) {
        this.mp.set(taskId, [priority, userId]);
        this.pq.enqueue([priority, taskId, userId]);
    }

    edit(taskId, newPriority) {
        // 懒修改
        const userId = this.mp.get(taskId)[1];
        this.add(userId, taskId, newPriority);
    }

    rmv(taskId) {
        // 懒删除
        this.mp.get(taskId)[0] = -1;
    }

    execTop() {
        while (!this.pq.isEmpty()) {
            const [priority, taskId, userId] = this.pq.dequeue();
            const [p, u] = this.mp.get(taskId);
            if (p === priority && u === userId) {
                this.rmv(taskId);
                return userId;
            }
            // else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        }
        return -1;
    }
}

###rust

use std::collections::{BinaryHeap, HashMap};

struct TaskManager {
    mp: HashMap<i32, (i32, i32)>, // taskId -> (priority, userId)
    h: BinaryHeap<(i32, i32, i32)>, // (priority, taskId, userId)
}

impl TaskManager {
    fn new(tasks: Vec<Vec<i32>>) -> Self {
        let mut manager = Self {
            mp: HashMap::new(),
            h: BinaryHeap::new(),
        };
        for task in tasks {
            manager.add(task[0], task[1], task[2]);
        }
        manager
    }

    fn add(&mut self, user_id: i32, task_id: i32, priority: i32) {
        self.mp.insert(task_id, (priority, user_id));
        self.h.push((priority, task_id, user_id));
    }

    fn edit(&mut self, task_id: i32, new_priority: i32) {
        // 懒修改
        let user_id = self.mp.get(&task_id).unwrap().1;
        self.add(user_id, task_id, new_priority);
    }

    fn rmv(&mut self, task_id: i32) {
        // 懒删除
        *self.mp.get_mut(&task_id).unwrap() = (-1, -1);
    }

    fn exec_top(&mut self) -> i32 {
        while let Some((priority, task_id, user_id)) = self.h.pop() {
            let (p, u) = self.mp[&task_id];
            if p == priority && u == user_id {
                self.rmv(task_id);
                return user_id;
            }
            // else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        }
        -1
    }
}

复杂度分析

  • 时间复杂度：
    • 初始化：$\mathcal{O}(n)$ 或者 $\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{tasks}$ 的长度。Python 和 Go 使用了堆化，复杂度是 $\mathcal{O}(n)$ 的。
    • $\texttt{add}$ 和 $\texttt{edit}$：$\mathcal{O}(\log (n+q))$，其中 $q$ 是 $\texttt{add}$ 和 $\texttt{edit}$ 的调用次数之和。
    • $\texttt{rmv}$：$\mathcal{O}(1)$。
    • $\texttt{execTop}$：均摊 $\mathcal{O}(\log (n+q))$。每个元素至多入堆出堆各一次。
  • 空间复杂度：$\mathcal{O}(n+q)$。

专题训练

见下面数据结构题单的「§5.6 懒删除堆」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

两种方法：有序集合 / 懒删除堆（Python/Java/C++/Go）

✇LeetCode 每日一题题解
endlesscheng

方法一：哈希表 + 有序集合

为了实现 $\texttt{find}$，我们需要对每个 $\textit{number}$ 创建一个有序集合，维护这个 $\textit{number}$ 对应的所有下标。用有序集合可以快速地获取最小下标。

对于 $\texttt{change}$，如果 $\textit{index}$ 处有数字，我们需要先删除旧的数字，所以还需要知道每个 $\textit{index}$ 对应的 $\textit{number}$ 是多少，这可以用一个哈希表记录。

具体来说，创建一个哈希表 $\textit{indexToNumber}$，以及一个哈希表套有序集合 $\textit{numberToIndices}$。

对于 $\texttt{change}$：

  • 如果 $\textit{index}$ 处有数字 $x$，那么从 $\textit{numberToIndices}[x]$ 中删除 $\textit{index}$（删除旧的数据）。
  • 然后，更新（或者插入）$\textit{indexToNumber}[\textit{index}] = \textit{number}$，往 $\textit{numberToIndices}[\textit{number}]$ 中添加 $\textit{index}$。

对于 $\texttt{find}$，获取 $\textit{numberToIndices}[\textit{number}]$ 中的最小元素即可。

class NumberContainers:
    def __init__(self):
        self.index_to_number = {}
        # from sortedcontainers import SortedSet
        self.number_to_indices = defaultdict(SortedSet)

    def change(self, index: int, number: int) -> None:
        # 移除旧数据
        old_number = self.index_to_number.get(index, None)
        if old_number is not None:
            self.number_to_indices[old_number].discard(index)

        # 添加新数据
        self.index_to_number[index] = number
        self.number_to_indices[number].add(index)

    def find(self, number: int) -> int:
        indices = self.number_to_indices[number]
        return indices[0] if indices else -1

class NumberContainers {
    private final Map<Integer, Integer> indexToNumber = new HashMap<>();
    private final Map<Integer, TreeSet<Integer>> numberToIndices = new HashMap<>();

    public void change(int index, int number) {
        // 移除旧数据
        Integer oldNumber = indexToNumber.get(index);
        if (oldNumber != null) {
            numberToIndices.get(oldNumber).remove(index);
        }

        // 添加新数据
        indexToNumber.put(index, number);
        numberToIndices.computeIfAbsent(number, _ -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        TreeSet<Integer> indices = numberToIndices.get(number);
        return indices == null || indices.isEmpty() ? -1 : indices.first();
    }
}

class NumberContainers {
    unordered_map<int, int> index_to_number;
    unordered_map<int, set<int>> number_to_indices;

public:
    void change(int index, int number) {
        // 移除旧数据
        auto it = index_to_number.find(index);
        if (it != index_to_number.end()) {
            number_to_indices[it->second].erase(index);
        }

        // 添加新数据
        index_to_number[index] = number;
        number_to_indices[number].insert(index);
    }

    int find(int number) {
        auto it = number_to_indices.find(number);
        return it == number_to_indices.end() || it->second.empty() ? -1 : *it->second.begin();
    }
};

// import "github.com/emirpasic/gods/v2/trees/redblacktree"
type NumberContainers struct {
indexToNumber   map[int]int
numberToIndices map[int]*redblacktree.Tree[int, struct{}]
}

func Constructor() NumberContainers {
return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree[int, struct{}]{}}
}

func (n NumberContainers) Change(index, number int) {
// 移除旧数据
if oldNumber, ok := n.indexToNumber[index]; ok {
n.numberToIndices[oldNumber].Remove(index)
}

// 添加新数据
n.indexToNumber[index] = number
if n.numberToIndices[number] == nil {
n.numberToIndices[number] = redblacktree.New[int, struct{}]()
}
n.numberToIndices[number].Put(index, struct{}{})
}

func (n NumberContainers) Find(number int) int {
indices, ok := n.numberToIndices[number]
if !ok || indices.Empty() {
return -1
}
return indices.Left().Key
}

复杂度分析

  • 时间复杂度：
    • 初始化 $\mathcal{O}(1)$。
    • $\texttt{change}$：$\mathcal{O}(\log q)$，其中 $q$ 是 $\texttt{change}$ 的调用次数。
    • $\texttt{find}$：$\mathcal{O}(\log q)$ 或者 $\mathcal{O}(1)$，取决于有序集合是否额外维护最小值。
  • 空间复杂度：$\mathcal{O}(q)$。

方法二：哈希表 + 懒删除堆

$\textit{numberToIndices}$ 改成哈希表套最小堆。

对于 $\texttt{change}$，不删除旧数据。

对于 $\texttt{find}$，查看堆顶是否等于 $\textit{number}$，若不相同，则意味着堆顶是之前没有删除的旧数据，弹出堆顶；否则堆顶就是答案。

class NumberContainers:
    def __init__(self):
        self.index_to_number = {}
        self.number_to_indices = defaultdict(list)

    def change(self, index: int, number: int) -> None:
        # 添加新数据
        self.index_to_number[index] = number
        heappush(self.number_to_indices[number], index)

    def find(self, number: int) -> int:
        indices = self.number_to_indices[number]
        while indices and self.index_to_number[indices[0]] != number:
            heappop(indices)  # 堆顶货不对板，说明是旧数据，删除
        return indices[0] if indices else -1

class NumberContainers {
    private final Map<Integer, Integer> indexToNumber = new HashMap<>();
    private final Map<Integer, PriorityQueue<Integer>> numberToIndices = new HashMap<>();

    public void change(int index, int number) {
        // 添加新数据
        indexToNumber.put(index, number);
        numberToIndices.computeIfAbsent(number, _ -> new PriorityQueue<>()).offer(index);
    }

    public int find(int number) {
        PriorityQueue<Integer> indices = numberToIndices.get(number);
        if (indices == null) {
            return -1;
        }
        while (!indices.isEmpty() && indexToNumber.get(indices.peek()) != number) {
            indices.poll(); // 堆顶货不对板，说明是旧数据，删除
        }
        return indices.isEmpty() ? -1 : indices.peek();
    }
}

class NumberContainers {
    unordered_map<int, int> index_to_number;
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> number_to_indices;

public:
    void change(int index, int number) {
        // 添加新数据
        index_to_number[index] = number;
        number_to_indices[number].push(index);
    }

    int find(int number) {
        auto& indices = number_to_indices[number];
        while (!indices.empty() && index_to_number[indices.top()] != number) {
            indices.pop(); // 堆顶货不对板，说明是旧数据，删除
        }
        return indices.empty() ? -1 : indices.top();
    }
};

type NumberContainers struct {
indexToNumber   map[int]int
numberToIndices map[int]*hp
}

func Constructor() NumberContainers {
return NumberContainers{map[int]int{}, map[int]*hp{}}
}

func (n NumberContainers) Change(index, number int) {
// 添加新数据
n.indexToNumber[index] = number
if _, ok := n.numberToIndices[number]; !ok {
n.numberToIndices[number] = &hp{}
}
heap.Push(n.numberToIndices[number], index)
}

func (n NumberContainers) Find(number int) int {
indices, ok := n.numberToIndices[number]
if !ok {
return -1
}
for indices.Len() > 0 && n.indexToNumber[indices.IntSlice[0]] != number {
heap.Pop(indices) // 堆顶货不对板，说明是旧数据，删除
}
if indices.Len() == 0 {
return -1
}
return indices.IntSlice[0]
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

复杂度分析

  • 时间复杂度：
    • 初始化 $\mathcal{O}(1)$。
    • $\texttt{change}$：$\mathcal{O}(\log q)$，其中 $q$ 是 $\texttt{change}$ 的调用次数。
    • $\texttt{find}$：均摊 $\mathcal{O}(\log q)$。
  • 空间复杂度：$\mathcal{O}(q)$。

专题训练

见下面数据结构题单的「§5.6 懒删除堆」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

❌