之前介绍了二叉堆的相关内容，这里继续前面的知识，介绍一下Heapify的内容，进而具体介绍另一种O(nlogn)的排序算法–堆排序。

Heapify

MAX-HEAPIFY

通过让A[i]的值在最大堆中shift down，从而使得下标i为根结点的子树重新遵循最大堆的性质。

参照《算法导论》给出相应伪码:

1
2
3
4
5
6
7
8
9
10
11
12
13
MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    # 找到i，i的左子树的根结点，i的右子树的根结点中值最大的结点
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r

    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

若值最大的结点不是i，则把最大的值跟i指定的值交换。然后继续对原值最大的结点递归进行MAX-HEAPIFY操作，若值最大的结点就是i，说明以i为根结点的子树已是最大堆，函数结束。

##BUILD-MAX-HEAP
构建最大堆，伪码：

1
2
3
4
BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = A.length/2 downto 1 #自底向上
        MAX-HEAPIFY(A, i)

HEAPSORT

堆排序的实现，伪码：

1
2
3
4
5
6
HEAPSORT(A)
    BUILD-MAX-HEAP(A) # 最大元素总是在根结点A[1]中
    for i = A.length downto 2
        exchange A[1] with A[i] # 将最大元素往后放在正确的位置i上
        A.heap-size = A.heap-size - 1 # 去掉结点n
        MAX-HEAPIFY(A, 1) # 维护，以保证去掉结点n后的堆还是最大堆

堆排序

实现思路

堆排序的实现思路关键就是上面HEAPIFY操作。

1.首先，构建最大堆
2.最大堆的一个性质：最大的元素就是堆顶的元素。我们每次就选择这个元素，这就像选择排序中选择的操作。我们这里不借助中间数组，直接和当前堆尾元素交换。
3.使最大元素在尾部不动，前面构成一个堆，维护这个堆，对其进行MAX-HEAPIFY，是前面变成最大堆
4.重复上述操作，在堆的规模缩小的同时，完成排序。

具体过程如下图：

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
heap_size = 0
left = lambda i: 2*i+1
right = lambda i: 2*i+2

def Heapify(arr, i):
    l, r = left(i), right(i)
    largest = l if l < heap_size and arr[l] > arr[i] else i
    largest = r if r < heap_size and arr[r] > arr[largest] else largest
    if i != largest:
        arr[i], arr[largest] = arr[largest], arr[i]
        Heapify(arr,largest)

def BuildMaxHeap(arr):
    global heap_size
    heap_size = len(arr)
    for i in range(len(arr)//2-1,-1,-1):
        Heapify(arr,i)

def HeapSort(arr):
    global heap_size
    BuildMaxHeap(arr)
    for i in range(len(arr)-1,-1,-1):
        arr[i], arr[0] = arr[0], arr[i]
        heap_size -= 1
        Heapify(arr,0)
    return arr

备注：很多情况下都使用arr[0]来维护堆的大小（算法导论中是采用的这种方式），这里为了直接返回排序的数组，并未这样处理，响应的规律也有所改变，但大同小异。