堆排序算法中的循环不变式

堆的特征

堆是一棵完全二叉树,且每个顶点的值都比左右孩子的值要大,这种堆称为最大堆;如果每个顶点的值都比其左右孩子的值要小,这种堆称为最小堆。 文章里面讨论的都是最大堆。堆有下面的的性质:

  • 顶点的值大于左右孩子的值
  • 堆的高度为堆元素数量的以2为底的对数值
  • 假设堆顶点的编号为i,则父节点的编号为1/2,左孩子编号为2i+1,右孩子编号为 2(i+1) (编号起始值为0)
  • 假设数组A表示一个堆,那么堆大小heap_size(A) <= len(A)

    堆排序

    关键子函数

    LEFT

    left 函数返回给定顶点的左孩子。

    right 函数返回给定顶点的右孩子。

    PARENT

    parent 函数返回给定顶点的父节点。

    VISIT HEAP

    visit heap 函数将一个数组按照堆的层数分离为子数组。

    代码

    def visit(A):
      n = len(A)
      height = int(math.log(n, 2)) + 1
      h = 0
      visted = []
      while h < height:
          h_visited = []
          start = 2**h - 1
          end = 2**(h+1) - 1
          j = start
          while j < end and j < n:
              h_visited.append(A[j])
              j = j + 1
          h = h + 1
          visted.append(h_visited)
      return visted
    

    MAX HEAPIFY

    max heapify 函数维持最大堆的特性。

    代码

    def max_heapify(A, i, heap_size):
      l = left(i)
      r = right(i)
      largest = i
      if l < heap_size and A[i] < A[l]:
          largest = l
      if r < heap_size and A[r] > A[largest]:
          largest = r
      # swap A[i] and A[largest]
      if largest != i:
          tmp = A[largest]
          A[largest] = A[i]
          A[i] = tmp
          # make sure heap A start with largest is a maximum heap
          max_heapify(A, largest, heap_size)
    

    BUILD MAX HEAP

    build max heap 构建一个最大堆。

    代码

    def build_max_heap(A):
      n = len(A)
      i = n/2
      # array index start with n/2 is leaf nodes in a heap
      # so make sure each parent is maxinum heap
      while i >= 0:
          max_heapify(A, i, n)
          i = i - 1
    

    HEAP SORT

    heap sort 函数使用堆的特性排序,算法思路是将无序的数组A构建为一个最大堆,此时顶点A[0]的值是最大值,然后交换A[0]与最后一个元素A[heap_size]的值,数组A违背了最大堆的特性,因此再次调用max heapify使得A变为最大堆,此时堆A的heap size为n-1。 上述循环一直到heap size为1结束。

    代码

    def heap_sort(A):
      build_max_heap(A)
      n = len(A)
      heap_size = n - 1
      while heap_size > 0:
          tmp = A[heap_size]
          A[heap_size] = A[0]
          A[0] = tmp
          max_heapify(A, 0, heap_size)
          heap_size = heap_size - 1
    

    循环不变式

    1. 不变式

    数组A[heap_size…n-1]在循环过程中以及结束的时候,保持为一个排序的数组。

    2. 初始

    初始时候,heap_size为n-1,数组A[n-1,n-1]中只有一个值,且这个值是最大堆A的顶点元素的值。不变式成立。

    3. 保持

    循环过程中,每次都将堆A的顶点值交换到数组A[heap_size, n-1],因此A[heap_size, n-1]是一个排序的数组。

    4. 结束

    当heap_size的值为0时,此时堆A中只有一个元素A[0],A[0]也是一个最大堆,且A[0, n-1]是一个有序数组。

    代码参考

    algorithm

关注公众号获得更多云最佳实践