输入：n个数的一个序列<a1,a2,...,an> (A[1..n]) 输出：输入序列的一个排序<b1,b2,...,bn>，满足b1≤b2≤...≤bn。

思想

参考：Wiki百科：堆排序 ## 堆表示堆的数组A包括两个属性：A.length给出数组元素的个数，A.heap-size表示有多少个堆元素存储在该数组中。也就是说，虽然A[1..A.length]可能都存有数据，但只有A[1..A.heap-size]中存放的是堆的有效元素。这里, 0 ≤ A.heap-size ≤ A.length。

（二叉）堆数组A是一个近似的完全二叉树，树的根结点是A[1]，这样，给定一个结点的下标i，它的父节点、左孩子和右孩子的下标：

1
2
3

PARENT(i) : return i/2 // i>>1
LEFT(i) : return 2i // i<<1
RIGHT(i) : return 2i+1 // i<<1 + 1

1. 最大堆：堆的最大元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。即：A[PARENT(i) ≥ A[i]。堆排序使用最大堆。 2. 最小堆：堆的最小元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不小于该子树根结点的值。即：A[PARENT(i) ≤ A[i]。最小堆常用来构造优先队列。

堆中结点的高度：该结点到叶结点最长简单路径上边的数目。堆的高度：根结点的高度。O(lgn)。其中，n为堆中元素个数。

实现

伪代码

# 时间复杂度：O(lgn)，维护最大堆性质的关键，假设根结点为LEFT(I)和RIGHT(i)的二叉树都是最大堆
# 通过让A[i]的值在最大堆中“逐级下降”，从而使得下标i为根结点的子树重新遵循最大堆的性质
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
    # 若值最大的结点不是i，则把最大的值跟i指定的值交换。
    # 然后继续对原值最大的结点递归进行MAX-HEAPIFY操作
    # 若值最大的结点就是i，说明以i为根结点的子树已是最大堆，函数结束
    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)
# 线性时间复杂度，从无序的输入数据数组中构造一个最大堆
BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = A.length/2 downto 1 #自底向上
        MAX-HEAPIFY(A, i)
# 时间复杂度：O(nlgn)，对一个数组进行原址排序(升序)
HEAPSORT(A)
    # 利用BUILD-MAX-HEAP将输入数组建成最大堆
    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后的堆还是最大堆

1. Python实现（升序）

heap_size = 0
LEFT = lambda i: 2*i+1
RIGHT = lambda i: 2*i+2 
# 维护最大堆
def HEAPIFY(A, i):
    l, r = LEFT(i), RIGHT(i)
    largest = l if l < heap_size and A[l] > A[i] else i # 最小堆则改为 A[l] < A[i]
    largest = r if r < heap_size and A[r] > A[largest] else largest # 最小堆则改为A[r] < A[largest]
    if i != largest:
        A[i], A[largest] = A[largest], A[i]
        HEAPIFY(A,largest)
# 构建最大堆
def BUILD_MAX_HEAP(A):
    global heap_size
    heap_size = len(A)
    for i in range(len(A)//2-1,-1,-1):
        HEAPIFY(A,i)
# 堆排序
def HEAPSORT(A):
    global heap_size
    BUILD_MAX_HEAP(A)
    for i in range(len(A)-1,-1,-1):
        A[i], A[0] = A[0], A[i]
        heap_size -= 1
        HEAPIFY(A,0)

注：降序排序仅需修改HEAPIFY中的比较，维护最小堆即可。

附：维护最大堆时进行的是尾部递归，这是一种比较低效的做法。修改为循环结构如下：

def HEAPIFY(A, i):
    while True:
        l, r = LEFT(i), RIGHT(i)
        largest = l if l < heap_size and A[l] > A[i] else i
        largest = r if r < heap_size and A[r] > A[largest] else largest
        if i == largest: break
        A[i], A[largest] = A[largest], A[i]
        i = largest

# 图片说明

## 复杂度 1. 空间复杂度：O(1), in-place排序 2. 最差/平均/最优时间复杂度：O(nlgn)

注意

维护堆的时候注意，表示左子树和右子树的下标都不能超出堆的大小。
堆排序时，注意调整堆的大小。

∞

九大排序算法及其Python实现之堆排序

思想

实现

注意