某储备粮的“学习笔记” - heap http://blog.gregwym.info/tag/heap/ zh-CN Wed, 06 Apr 2011 04:57:39 +0800 Wed, 06 Apr 2011 04:57:39 +0800 CS 240复习总结之二: Priority Queues http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-er--priority-queues.html http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-er--priority-queues.html Wed, 06 Apr 2011 04:57:39 +0800 咳嗽di小鱼 Priority Queue 的基础操作:

  • insert: 在Queue中加入一个带有对应优先级的item
  • deleteMax: 移除优先级最高的item (此操作仅适用于maximum-oriented priority queue)
  • deleteMin: 移除优先级最低的item (此操作仅适用于minimum-oriented priority queue)

三种Implementation:

  1. 无序array (selection sort)

    • insert: O(1)
    • delete: O(n)
  2. 有序array (insertion sort)

    • insert: O(n)
    • delete: O(1)
  3. Heap (一种BST)

    • insert: O(log n)
    • delete: O(log n)

Heap的性质:

  1. 从上到下, 从左到右, 必须在一层(level)填满以后再使用下一层
  2. parent的优先级必须大于等于(小于等于 for min-heap)其children的优先级
  3. Heap的高度是Θ(log n)

Heap Insertion:

  • 将新item放入第一个空闲的位置 (参考heap的第一条性质)
  • 对其执行bubble-up, 直到符合所有heap性质
    #bubble-up:



    while [parent(v) exists and key(parent(v)) < key(v)] do 
        swap v and parent(v) v <- parent(v)
    

Heap deleteMax/Min:

  • 用heap中的最后一个item取代root
  • 对其执行bubble-down, 直到符合所有heap性质



    bubble-down



    while [v is not a leaf] do 
        u <- child of v with largest key 
        if key(u) > key(v) then 
            swap v and u v <- u 
        else 
            break
    

Heap array的特点 (当前item的位置为i):

  • Left child位于2i+1
  • Right child位于2i+2
  • Parent位于floor[(i-1)/2]

建立heap的两种方法:

  • 以空heap为起始, 逐个item执行insert
  • 以含有n个item的array为起始, 从index为floor[(n-1)/2]的item开始, 逐个执行bubble-down, 直到index 0

注: 使用第二种方法建立heap, 然后执行k次deleteMax/Min, 可快速查找array中第k大的iterm. 运行时间为Θ(n + k log n)

其他方法请参考: 找数组/VECTOR内第K大的数

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/

]]>
0 http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-er--priority-queues.html#comments http://blog.gregwym.info/feed/cs-240-fu-xi-zong-jie-zhi-er--priority-queues.html