是否存在插入log查询和弹出O(1)的堆

ppip @ 2024-04-30 17:56:15

by critnos @ 2024-04-30 18:10:37

不懂。弹出次数不是 <= 插入次数，所以弹出就算是 log 也可以被摊到插入上吗

by critnos @ 2024-04-30 18:12:28

是不是可持久化啥的

by Bingxiu @ 2024-04-30 18:26:19

@ppip 啊？如果弹出 O(1)，说明平衡性可以 O(1) 维护，那这样不就说明插入也可以 O(1) 吗？大佬我不懂

by yummy @ 2024-04-30 18:39:50

@ppip 我觉得跳表（skip list）可以做到，可惜弹出是期望 O(1)，插入是期望 O(\log n)。

by WydnksqhbD @ 2024-04-30 18:41:22

Cu ball

by ppip @ 2024-04-30 18:42:11

@critnos 类似的吧，就是要求非均摊的复杂度

by ppip @ 2024-04-30 18:44:13

@yummy 弹出不用向上找每一个表吗

by yummy @ 2024-04-30 18:49:52

@ppip 不是啊，弹出只要对期望 O(1) 个链表 pop_front 啊/kel

（我只是从信息技术书上看到这个数据结构，没有认真写过，纯口胡）

by ppip @ 2024-04-30 18:50:21

@Bingxiu 我不太懂详细的信息理论，但是暴力维护有序序列应该是查询O(1)弹出O(1)但是插入做不到O(1)的吧

by critnos @ 2024-04-30 18:52:17

@ppip 这个你直接平衡树，每个点维护个指向后继的指针，再维护最小值的位置就行了吧。