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

[sulinehk]

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

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

找最大要常量时间

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

[Vegetable]

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

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

[sulinehk]

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

[sulinehk]

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

[leoaqr]

@sulinehk 插入任意应该是 logn

[sulinehk]

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

[sulinehk]

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

[leoaqr]

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

[sulinehk]

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

[jedihy]

@leoaqr 这是有序数组

[leoaqr]

@jedihy 有序数组不影响啊

[leoaqr]

@sulinehk 对

[jedihy]

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

[leoaqr]

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

[jedihy]

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

[sulinehk]

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