# 算法导论详解(5) 第六章 堆排序

xiaoxiao2021-02-28  6

## 堆(6.1, P84)

def PARENT(i): return i / 2 def LEFT(i): return 2 * i def RIGHT(i): return 2 * i + 1

## 维持堆的性质（6.2，P86）

MAX-HEAPIFY：输入为一个数组A和一个下标i，A[i]有可能小于其孩子，通过让A[i]在数组中“逐级下降”，从而使得以下标i为根节点的子树重新遵循最大堆的性质。

Python实现为：

def MAX_HEAPIFY(A, i): l = LEFT(i) r = RIGHT(i) largest = -1 if l <= len(A) and A[l - 1] > A[i - 1]: largest = l else: largest = i if r <= len(A) and A[r - 1] > A[largest - 1]: largest = r if largest != i: A[i - 1], A[largest - 1] = A[largest - 1], A[i - 1] MAX_HEAPIFY(A, largest)

T(n)=T(2n/3)+Θ(1) 上述递归式的解为： T(n)=O(lgn)

## 建堆(6.3, P87)

Python实现为：

from math import floor def BUILD_MAX_HEAP(A): heap_size = len(A) for i in range(int(floor(heap_size / 2)), 0, -1): MAX_HEAPIFY(A, i)

BUILD_MAX_HEAP 的时间复杂度为 T(n)=O(n)

## 堆排序算法(6.4，P89)

Python实现：

def HEAPSORT(A): BUILD_MAX_HEAP(A) heap_size = len(A) for i in range(len(A), 1, -1): A[1 - 1], A[i - 1] = A[i - 1], A[1 - 1] # exchage A[i] with A[1] heap_size = heap_size - 1 MAX_HEAPIFY(A, 1, heap_size)

HEAPSORT过程的时间复杂度为： O(nlgn) ，因为BUILD_MAX_HEAP的时间复杂度为 O(n) ，n-1次调用MAX_HEAPIFY，每次时间为 O(lgn)

## 堆排序的Python完整实现

from math import floor def PARENT(i): return i / 2 def LEFT(i): return 2 * i def RIGHT(i): return 2 * i + 1 def MAX_HEAPIFY(A, i, size): l = LEFT(i) r = RIGHT(i) largest = -1 if l <= size and A[l - 1] > A[i - 1]: largest = l else: largest = i if r <= size and A[r - 1] > A[largest - 1]: largest = r if largest != i: A[i - 1], A[largest - 1] = A[largest - 1], A[i - 1] MAX_HEAPIFY(A, largest, size) def BUILD_MAX_HEAP(A): heap_size = len(A) for i in range(int(floor(heap_size / 2)), 0, -1): MAX_HEAPIFY(A, i, heap_size) def HEAPSORT(A): BUILD_MAX_HEAP(A) heap_size = len(A) for i in range(len(A), 1, -1): A[1 - 1], A[i - 1] = A[i - 1], A[1 - 1] # exchage A[i] with A[1] heap_size = heap_size - 1 MAX_HEAPIFY(A, 1, heap_size) if __name__ == "__main__": # A = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] # MAX_HEAPIFY(A, 2) # for i in range(0, len(A)): # print(A[i], end=" ") # A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] # BUILD_MAX_HEAP(A) # for i in range(0, len(A)): # print(A[i], end=" ") A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] HEAPSORT(A) for i in range(0, len(A)): print(A[i], end=" ")

## 优先队列(6.5，P90)

def HEAP_MAXIMUM(A): return A[1] def HEAP_EXTRACT_MAX(A, heap_size): if heap_size < 1: print("ERROR!! Heap underflow!!") return -1 max_A = A[1 - 1] A[1 - 1] = A[heap_size - 1] heap_size = heap_size - 1 MAX_HEAPIFY(A, 1, heap_size) return max_A

HeapExtractMax的操作复杂度为 O(lgn) （也就是MAX_HEAPIFY的复杂度）。

## 最大优先队列的Python完整实现：

def PARENT(i): return i / 2 def LEFT(i): return 2 * i def RIGHT(i): return 2 * i + 1 def MAX_HEAPIFY(A, i, heap_size): l = LEFT(i) r = RIGHT(i) largest = -1 if l <= heap_size and A[l - 1] > A[i - 1]: largest = l else: largest = i if r <= heap_size and A[r - 1] > A[largest - 1]: largest = r if largest != i: A[i - 1], A[largest - 1] = A[largest - 1], A[i - 1] MAX_HEAPIFY(A, largest, heap_size) def HEAP_MAXIMUM(A): return A[1] def HEAP_EXTRACT_MAX(A, heap_size): if heap_size < 1: print("ERROR!! Heap underflow!!") return -1 max_A = A[1 - 1] A[1 - 1] = A[heap_size - 1] heap_size = heap_size - 1 MAX_HEAPIFY(A, 1, heap_size) return max_A def HEAP_INCREASE_KEY(A, i, key): if key < A[i - 1]: print("ERROR!! New key is smaller than current key!!!") return A[i - 1] = key while i > 1 and A[int(PARENT(i) - 1)] < A[int(i - 1)]: A[int(PARENT(i) - 1)], A[int(i - 1)] = A[int(i - 1)], A[int(PARENT(i) - 1)] i = PARENT(i) def MAX_HEAP_INSERT(A, key): MAX_INT = 0x7fffffff heap_size = len(A) + 1 A.append(- MAX_INT) # 尾部追加元素 HEAP_INCREASE_KEY(A, heap_size, key) if __name__ == "__main__": A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] MAX_HEAP_INSERT(A, 9) # 调用的数值都是从1开始。 for i in range(0, len(A)): print(A[i], end=" ")