Sync Heap: 先删除，后提问

Lobsters Hottest 2026/08/25 17:22 论文

摘要

本文介绍了 sync heap，一种新颖的数据结构，它将删除操作与揭示被删除元素解耦，使得在有限检查下插入和删除操作具有常数摊销时间复杂度，并将一个教科书中的调度问题从 O(n log n) 改进到 O(n)。

查看原文

查看缓存全文

缓存时间: 2026/08/25 17:45

# 同步堆：先删除，再询问
来源：https://arxiv.org/abs/2608.07134
查看PDF (https://arxiv.org/pdf/2608.07134)

> 摘要：堆（优先队列）是计算机科学中被研究得最透彻的数据结构之一。本文对教科书中的一项传统假设进行了批判性反思，该假设认为在比较模型中，插入元素和删除最小值这两个标准的堆操作中至少有一个必须耗费对数时间。通过将删除操作本身与向用户揭示被删除元素身份这一行为解耦，我们突破了排序障碍，并在堆操作复杂度之间建立了一种全新的权衡关系。这表明，对数级障碍并非删除最小值操作本身固有的代价，而是立即获知哪个元素被删除所带来的信息代价。在用户仅以常数次频率检查堆状态的特殊情况下，我们证明了插入和删除操作均可以均摊常数时间实现。作为一个应用，我们将一个教科书式的单位时间调度问题的运行时间从 $\mathcal{O}(n \log n)$ 改进到了最优的 $\mathcal{O}(n)$。我们的成果是通过设计一种新的数据结构——同步堆——而获得的，该结构通过重排和压缩其操作来提升速度，直到查询迫使它进行同步并揭示其状态。作为一个关键组件，我们使用了Chazelle在其最小生成树算法中引入的软堆。我们的数据结构简单、基于比较且是确定性的，我们的结果在渐进意义上是最优的。

## 提交历史

来自：Egor Gorbachev [查看邮件 (https://arxiv.org/show-email/205aaaa6/2608.07134)] **[版本1]** 2026年8月7日，星期五，11:53:20 UTC (35 KB)