在看算法 C 语言实现有个关于优先队列的问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2155 天前的主题，其中的信息可能已经有所发展或是发生改变。

书上写有序数组实现优先队列时

删除要线性时间这个能理解移动数组的开销

找最大要常量时间

为什么删除最大只用常量时间？是书写错了嘛？

队列

用常量

要常量

数组

15 条回复 • 2018-12-31 16:14:24 +08:00

Vegetable

2018-12-30 12:43:19 +08:00 via Android

从小到大的有序数组删除最后一个元素是常量，删除第一个是线性
查找最小和最大是常量
删除任意一个是线性，插入任意一个也是线性。
删除最大就是出列操作，队列的出列设计成常量时间也是很合理的。

因为是删除最后一个元素，不需要移动其他的，自然就是 o1

sulinehk

2018-12-30 12:47:48 +08:00 via Android

@Vegetable 删除最大是常量我理解了但是为什么删除任意也是常量？懒删除吗？

sulinehk

2018-12-30 12:51:13 +08:00 via Android

@Vegetable 看错了看错了删除任意是线性插入任意也是线性谢谢

leoaqr

2018-12-30 17:05:52 +08:00 via iPhone

@sulinehk 插入任意应该是 logn

sulinehk

2018-12-30 19:53:22 +08:00 via Android

@leoaqr 二分插入才是 lgn 书上写的是普通插入

sulinehk

2018-12-30 20:01:56 +08:00 via Android

@leoaqr 不对好像二分插入也是线性先二分搜索要 lgn 再移位要线性加起来大 O 线性？

leoaqr

2018-12-30 21:06:10 +08:00 via iPhone

@sulinehk 插入就是一遍 botton-up 就完成了，如果 value 比 parenr value 大就 swap，不然就停止了，所以就是 logn

sulinehk

2018-12-31 02:40:05 +08:00 via Android

@leoaqr 就堆的自底向上堆化是吧？

jedihy

2018-12-31 02:55:09 +08:00 via iPhone

@leoaqr 这是有序数组

leoaqr

2018-12-31 05:02:02 +08:00 via iPhone

@jedihy 有序数组不影响啊

leoaqr

2018-12-31 05:02:11 +08:00 via iPhone

@sulinehk 对

jedihy

2018-12-31 06:10:37 +08:00 via iPhone

@leoaqr 有序数组没有堆的性质，怎么 bottom up ？按你的描述就是 o(n)。

leoaqr

2018-12-31 06:14:12 +08:00 via iPhone

@jedihy 有序数组有堆的性质，反之不成立。

jedihy

2018-12-31 09:20:20 +08:00

@leoaqr 有堆的性质并不代表你能用堆的办法插进去，因为你不能保证插入完数组还是有序的。

sulinehk

2018-12-31 16:14:24 +08:00 via Android

@jedihy 对哦堆的性质应该是比有序数组松的 134 有序数组插入 2 1243 最小堆