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

堆的特征

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

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

  堆排序

  关键子函数

  LEFT

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

  RIGHT

  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