算法导论第六章

堆性质的维护

• 复杂度 $O(\log n)$

  def MaxHeapIFY(lis, pos, heapsize):
      while 2*pos+1 < heapsize:
          if 2*pos+2 < heapsize:
              left = lis[2*pos+1]
              right = lis[2*pos+2]
              root = lis[pos]
              if left > root and left > right:
                  lis[pos] = left
                  lis[2*pos+1] = root
                  MaxHeapIFY(lis, 2*pos+1, heapsize)
              elif right > root and right > left:
                  lis[pos] = right
                  lis[2*pos+2] = root
                  MaxHeapIFY(lis, 2*pos+2, heapsize)
              else:
                  return lis
          else:
              left = lis[2*pos+1]
              root = lis[pos]
              if left > root:
                  lis[pos] = left
                  lis[2*pos+1] = root
                  MaxHeapIFY(lis, 2*pos+1, heapsize)
              else:
                  return lis
      return lis

建堆

• 复杂度 $O(n)$

  def BuildMaxHeap(lis, heapsize):
      for pos in range(heapsize-1,-1,-1):
          MaxHeapIFY(lis, pos, heapsize)
      return lis

堆排序

• 复杂度 $O(n \log n)$
• 原址排序

  def HeapSort(lis):
      for heapsize in range(len(lis),0,-1):
          BuildMaxHeap(lis, heapsize)
          largest = lis[0]
          lis[0] = lis[heapsize-1]
          lis[heapsize-1] = largest
      return lis

优先队列

• 返回最大元素 $\Theta(1)$
• 插入新元素 $O(\log n)$
• 去掉并返回最大元素 $O(\log n)$
• 更新某一元素 $O(\log n)$