Home
Sign Up
Sign In
V2EX
›
问与答
在看算法 C 语言实现有个关于优先队列的问题
sulinehk
·
Dec 30, 2018
via Android · 2927 views
This topic created in 2879 days ago, the information mentioned may be changed or developed.
书上写有序数组实现优先队列时
删除要线性时间 这个能理解 移动数组的开销
找最大要常量时间
为什么删除最大只用常量时间?是书写错了嘛?
队列
用常量
要常量
数组
15 replies
•
2018-12-31 16:14:24 +08:00
Vegetable
Dec 30, 2018 via Android
1
1
从小到大的有序数组删除最后一个元素是常量,删除第一个是线性
查找最小和最大是常量
删除任意一个是线性,插入任意一个也是线性。
删除最大就是出列操作,队列的出列设计成常量时间也是很合理的。
因为是删除最后一个元素,不需要移动其他的,自然就是 o1
sulinehk
OP
Dec 30, 2018 via Android
2
@
Vegetable
删除最大是常量我理解了 但是为什么删除任意也是常量?懒删除吗?
sulinehk
OP
Dec 30, 2018 via Android
3
@
Vegetable
看错了看错了 删除任意是线性 插入任意也是线性 谢谢
leoaqr
Dec 30, 2018 via iPhone
4
@
sulinehk
插入任意应该是 logn
sulinehk
OP
Dec 30, 2018 via Android
5
@
leoaqr
二分插入才是 lgn 书上写的是普通插入
sulinehk
OP
Dec 30, 2018 via Android
6
@
leoaqr
不对 好像二分插入也是线性 先二分搜索要 lgn 再移位要线性 加起来大 O 线性?
leoaqr
Dec 30, 2018 via iPhone
7
@
sulinehk
插入就是一遍 botton-up 就完成了,如果 value 比 parenr value 大就 swap,不然就停止了,所以就是 logn
sulinehk
OP
Dec 31, 2018 via Android
8
@
leoaqr
就堆的自底向上堆化是吧?
jedihy
Dec 31, 2018 via iPhone
9
@
leoaqr
这是有序数组
leoaqr
Dec 31, 2018 via iPhone
10
@
jedihy
有序数组不影响啊
leoaqr
Dec 31, 2018 via iPhone
11
@
sulinehk
对
jedihy
Dec 31, 2018 via iPhone
12
@
leoaqr
有序数组没有堆的性质,怎么 bottom up ?按你的描述就是 o(n)。
leoaqr
Dec 31, 2018 via iPhone
13
@
jedihy
有序数组有堆的性质,反之不成立。
jedihy
Dec 31, 2018
14
@
leoaqr
有堆的性质并不代表你能用堆的办法插进去,因为你不能保证插入完数组还是有序的。
sulinehk
OP
Dec 31, 2018 via Android
15
@
jedihy
对哦 堆的性质应该是比有序数组松的 134 有序数组 插入 2 1243 最小堆
About
·
Help
·
Advertise
·
Blog
·
API
·
FAQ
·
Privacy
·
Solana
·
1013 Online
Highest 6679
·
Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 26ms ·
UTC 22:07
·
PVG 06:07
·
LAX 14:07
·
JFK 17:07
♥ Do have faith in what you're doing.
❯