堆数据结构是数组对象，它可以用近似完全二叉树进行表示。例如下面数组A，可以表示成a图的二叉树形式。
设一节点的索引为i，从上图可以看到，其父节点的索引和子节点的索引与该节点的索引有如下关系： p a r e n t ( i ) = i / / 2 ( / / 表 示 取 整 ) parent(i) = i//2 \quad(// 表示取整)\\ parent(i)=i//2(//表示取整)
l e f t ( i ) = 2 i left(i) = 2i\\ left(i)=2i
r i g h t ( i ) = 2 i + 1 right(i) = 2i + 1\\ right(i)=2i+1
例如，元素14的索引为2，其父节点索引为2//2 = 1，左子节点索引为2x2 = 4, 右子节点为2x2+1 = 5
堆有最大堆（max heaps）和最小堆（min heaps）结构，两种结构分别满足不同的特性。对于max heaps，除根节点外，所有节点的父节点的值要大于或等于该节点的值。也即： A [ p a r e n t ( i ) ] ≥ A [ i ] A[parent(i)] \ge A[i] A[parent(i)]≥A[i] 对于min heaps，其特性刚好相反：
A [ p a r e n t ( i ) ] ≤ A [ i ] A[parent(i)] \le A[i] A[parent(i)]≤A[i] 但是任意给出一个数组，不一定满足堆的上述特性，因此需要相应的操作来保持堆的特性，下面以max heaps为例，讲述堆的相关操作。
max heapify是用来保持堆的特性，对某一节点，判断该节点是否满足堆的特性，如果不满足则将该节点移动合适的位置。
如上图，元素4不满足最大堆的特性因为它要比14和7都要小，因此4需要和14和7中最大的一个元素互换位置，以保证父节点的值大于等于子节点的值。互换位置后再次判断是否满足特性，这时仍然不满足，因此需要再次移动直到图c的位置。
当移动节点后仍然是进行相同的操作：判断是否满足特性，不满足则移动。因此可以用递归的方式进行编写代码，程序的时间复杂度为O(logn)。
def heapify(arr, n, i): """ arr:数组 n：数组的长度 i: 当前节点的索引 """ r = 2*i + 1 l = 2*i # 判断左子节点是否大于当前节点 if l < n and arr[l] > arr[i]: largest = l else: largest = i # 判断右子节点是否大于当前节点 if r < n and arr[r] > arr[largest]: largest = r # 不满足特性，交换节点位置，交换后再次进行heapify if largest is not i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)有了上述操作后，我们就可以根据数组来建立max heaps.
堆的本质还是一个数组，Max-Heapify只是改变了元素的位置，使其满足最大堆的特性，因此需要对每一个元素检查其是否满足特性。但是A[n/2 + 1,…,n]这部分的元素都是子节点，因为2(n/2 + 1)>n，超出了索引范围，为此我们只需考虑前半部分的元素，其时间复杂度可以很容易得分析出为O(nlogn)。
def build_max_heaps(arr, n): i = n//2 while i >= 0: heapify(arr, n, i) i -= 1建立好的最大堆如图c，第一个元素是数组中的最大的元素，而索引靠后的元素是数组中较小的元素。如果我们需要升序排序，那么每一次可以将第一个元素和最后一个元素交换，改变数组的元素排列。交换后利用max-heapify，保持最大堆特性，这时第一个元素是前n-1个元素中最大的元素，将其放在n-1的位置处，以此类推即可完成排序。
def heapSort(arr): n = len(arr) build_max_heaps(arr, n) for k in range(n-1, 0, -1): arr[k], arr[0] = arr[0], arr[k] heapify(arr, k, 0) arr = [13, 11, 12, 5, 6, 7] heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print(" {}".format(arr[i]), end="") # output: # Sorted array is # 5 6 7 11 12 13整个程序的时间复杂度为O(nlogn)
