一个定时任务系统常驻 100 万个待触发任务，按触发时间排序，每秒新增 2000 个、触发 2000 个。业务还要求能按 taskId 取消任务，取消率约 5%，且被取消的任务大多还没到期。你用二叉堆怎么实现？直接遍历堆去找 taskId 的代价是多少？如果不想付这个代价，你会怎么设计？

面试官在考什么

考察是否理解堆只能高效拿到极值、不支持按 key 高效定位，以及索引堆/懒删除/时间轮之间的工程取舍。

堆与优先队列

回答框架 · 前两步

1. 二叉堆取堆顶 O(1)，插入/弹出 O(log n)，100 万规模的 log2(10^6)≈20 次比较，每秒 4000 次操作绰绰有余，量级完全匹配。
2. 取消的痛点在'定位'而不是'删除'：堆不支持按 taskId 查找，线性扫描是 O(n)=100 万次，5% 取消率下每秒上百次取消意味着上亿次比较，不可行。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 有个排行榜模块：N=10^6 个用户按分数从高到低存在一个容器里，读取非常频繁（每秒约 10^5 次「取第 k 名」和「取某用户的排名」），写入很少（每秒约 10 次插入/删除，插入位置随机分布在容器中部）。同事建议用双向链表，理由是插入删除 O(1)；你倾向用哪一种？请从内存布局、常数开销和这两类操作的实际耗时量级给出判断依据。
• 内存里要维护 50 万条按时间排序的订单快照，需要支持三种操作：① 按下标随机读取（约 5000 QPS，要拿到第 k 早的订单）；② 在任意位置插入新订单（约 200 次/秒，插入位置在 [0, 50万] 上近似均匀分布）；③ 按订单号删除（约 200 次/秒，位置同样近似均匀分布）。你会选动态数组还是双向链表？请给出量化判断依据：涉及哪些开销、量级差多少。如果业务要求三种操作都不能慢，你会怎么改造这个结构？
• 某服务在内存里维护一份“最近 N 条记录”的有序表（N=100 万，单条记录 64B），线上埋点统计的操作占比是：尾部追加 90%，按序号随机读取 9%，在中间指定位置插入或删除 1%。现有实现是动态数组，中间插入需要 memmove 平均约 50 万条记录（约 32MB）。有同学提议整体换成双向链表，理由是“链表插入删除是 O(1)”。作为技术负责人，你怎么做这个决策？请给出你的判断依据、你要补测的数据，以及最终方案。
• 在一个长度为 100 万的整型序列上，需要执行 10 万次操作。其中 90% 是在序列头部插入一个元素，10% 是按索引随机读取一个元素。你会选择数组还是单链表？请分别估算两种选择下这 10 万次操作的相对代价（不需要精确时间，说明量级即可）。如果把比例改成 90% 随机读取、10% 头部插入，你的选择会变吗？为什么？
• 给你一个长度 n=10^7 的整数数组和一个固定窗口大小 k=1000，要求输出每个窗口内的最大值，总时间必须是 O(n)。你会用什么结构？请具体说明：队列里存元素值还是下标、什么时候从队尾弹出、队首元素什么时候失效、以及为什么这套操作合起来是 O(n) 而不是 O(nk)。
• 一个下单服务每秒产生约 8 万条事件，由一个后台线程批量拉取（每 50ms 一次）后写下游消息队列。缓冲放在进程内存里，消费者偶发卡顿 2~3 秒。请给出你选的有界队列实现和容量参数：为什么不用无界的 LinkedBlockingQueue？容量大概设多少、内存占多少？消费者卡顿 3 秒导致队列满时，你的策略是阻塞生产者、丢弃、还是落盘？如果改成单生产者单消费者的无锁环形缓冲区，生产者和消费者各需要维护什么状态，怎么判断'空'和'满'？