Sync Heap: 先删除，后提问

Lobsters Hottest 论文
data-structures algorithms priority-queues theoretical-cs optimization

摘要

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

<p><a href="https://lobste.rs/s/a371nr/sync_heap_delete_first_ask_questions">评论</a></p>
查看原文
查看缓存全文

缓存时间: 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)

相似文章

过早优化有时也挺有趣

Lobsters Hottest

一篇探讨为存储ping时间戳优化环形缓冲区数据结构的博客文章，讨论了标签联合、位域和结构体填充以减少内存占用。

观察 Go 的新垃圾回收器在堆中的移动

Lobsters Hottest

Go 1.26 将 Green Tea 设为默认垃圾回收器，提升了缓存友好性。本文通过 Go 和 C# 可视化堆分配，并讨论了非移动回收器和稀疏页面带来的挑战。

Rust 零拷贝页面：我是如何停止焦虑并爱上生命周期的

Hacker News Top

# Rust 零拷贝页面：我是如何停止焦虑并爱上生命周期的 来源：[https://redixhumayun.github.io/databases/2026/04/14/zero-copy-pages-in-rust.html](https://redixhumayun.github.io/databases/2026/04/14/zero-copy-pages-in-rust.html) *你可以在[这里](https://github.com/redixhumayun/simpledb/)找到该项目的源代码* 零拷贝是一种旨在消除内核与用户空间缓冲区之间 CPU 数据复制的技术，尤其在数据处理等高吞吐量应用中极具价值。