V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
sulinehk
V2EX  ›  问与答

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

  •  
  •   sulinehk · 2018-12-30 12:28:37 +08:00 via Android · 1823 次点击
    这是一个创建于 2153 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    找最大要常量时间

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

    15 条回复    2018-12-31 16:14:24 +08:00
    Vegetable
        1
    Vegetable  
       2018-12-30 12:43:19 +08:00 via Android   ❤️ 1
    从小到大的有序数组删除最后一个元素是常量,删除第一个是线性
    查找最小和最大是常量
    删除任意一个是线性,插入任意一个也是线性。
    删除最大就是出列操作,队列的出列设计成常量时间也是很合理的。

    因为是删除最后一个元素,不需要移动其他的,自然就是 o1
    sulinehk
        2
    sulinehk  
    OP
       2018-12-30 12:47:48 +08:00 via Android
    @Vegetable 删除最大是常量我理解了 但是为什么删除任意也是常量?懒删除吗?
    sulinehk
        3
    sulinehk  
    OP
       2018-12-30 12:51:13 +08:00 via Android
    @Vegetable 看错了看错了 删除任意是线性 插入任意也是线性 谢谢
    leoaqr
        4
    leoaqr  
       2018-12-30 17:05:52 +08:00 via iPhone
    @sulinehk 插入任意应该是 logn
    sulinehk
        5
    sulinehk  
    OP
       2018-12-30 19:53:22 +08:00 via Android
    @leoaqr 二分插入才是 lgn 书上写的是普通插入
    sulinehk
        6
    sulinehk  
    OP
       2018-12-30 20:01:56 +08:00 via Android
    @leoaqr 不对 好像二分插入也是线性 先二分搜索要 lgn 再移位要线性 加起来大 O 线性?
    leoaqr
        7
    leoaqr  
       2018-12-30 21:06:10 +08:00 via iPhone
    @sulinehk 插入就是一遍 botton-up 就完成了,如果 value 比 parenr value 大就 swap,不然就停止了,所以就是 logn
    sulinehk
        8
    sulinehk  
    OP
       2018-12-31 02:40:05 +08:00 via Android
    @leoaqr 就堆的自底向上堆化是吧?
    jedihy
        9
    jedihy  
       2018-12-31 02:55:09 +08:00 via iPhone
    @leoaqr 这是有序数组
    leoaqr
        10
    leoaqr  
       2018-12-31 05:02:02 +08:00 via iPhone
    @jedihy 有序数组不影响啊
    leoaqr
        11
    leoaqr  
       2018-12-31 05:02:11 +08:00 via iPhone
    jedihy
        12
    jedihy  
       2018-12-31 06:10:37 +08:00 via iPhone
    @leoaqr 有序数组没有堆的性质,怎么 bottom up ?按你的描述就是 o(n)。
    leoaqr
        13
    leoaqr  
       2018-12-31 06:14:12 +08:00 via iPhone
    @jedihy 有序数组有堆的性质,反之不成立。
    jedihy
        14
    jedihy  
       2018-12-31 09:20:20 +08:00
    @leoaqr 有堆的性质并不代表你能用堆的办法插进去,因为你不能保证插入完数组还是有序的。
    sulinehk
        15
    sulinehk  
    OP
       2018-12-31 16:14:24 +08:00 via Android
    @jedihy 对哦 堆的性质应该是比有序数组松的 134 有序数组 插入 2 1243 最小堆
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1125 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 18:39 · PVG 02:39 · LAX 10:39 · JFK 13:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.