- Published on
堆排序算法中的循环不变式
- Authors
- Name
- Mao
堆的特征
堆是一棵完全二叉树，且每个顶点的值都比左右孩子的值要大，这种堆称为最大堆；如果每个顶点的值都比其左右孩子的值要小，这种堆称为最小堆。 文章里面讨论的都是最大堆。堆有下面的的性质：
- 顶点的值大于左右孩子的值
- 堆的高度为堆元素数量的以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 函数将一个数组按照堆的层数分离为子数组。
代码
n
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 函数维持最大堆的特性。
代码
n
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 构建一个最大堆。
代码
n
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结束。
代码
n
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]是一个有序数组。