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/