在看搜索引擎做查询结果排序的用到了堆排序，特来复习一下。 那么在深入堆排序之前先来列举一下常见的排序方法，Insertion sort ，最简单直观的排序方法，时间复杂度最坏O(n2 )，in place(Recall that a sorting algorithm sorts in place if only a constant number of elements of the input array are ever stored outside the array.)就是说除了输入数组，仅还需耗费常数大小的空间， 这里对于insert sorting，应该只在交换element时，需要一个element的额外的暂存空间。此方法适用于size很小的输入。Merge sort ，基于分治的一种排序算法，时间复杂度O(nlgn)，但不是in place的，明显merge的时候需要较多的额外空间。Heap sort ，我们下面要介绍的，时间复杂度O(nlgn), 而且是in place的。Quick sort , 快排，最差时间复杂度O(n2 ),平均的时间复杂度为O(nlgn),但是据说在实际引用时比堆排序高效。 下面开始介绍heap sort, 那么堆排序当然核心就是堆这个数据结构，堆是个完全二叉树，而且每个节点都比左右子节点大（或小），因为堆分为max堆和min堆。 完全二叉树有个非常高效的存储方法，就是数组，一般的树都要用链表去存储。 对于heap sort的输入数组，如A[16,4,10,14,7,9,3,2,8,1]，要进行堆排序，首先要建堆，建堆可以分为两步： 将输入数组抽象成完全二叉树 建堆BUILD-MAX-HEAP 那么上面的输入数组可以抽象成如下的二叉树， 16 4 10 14 7 9 3 2 8 1 那么一般你必须去记录这个树结构，对吧，一般用链表来记录节点，节点的左右子节点的指针，这样就需要耗费比输入数组多几倍的空间，这样就无法in place了。 妙就妙在，你根据输入数组依次建立的这个完全二叉树，不用任何额外的空间去记录。这就得益于完全二叉树本身就是可以用数组存储的，这种数据结构是非常高效的。 对于数组中任一节点，你想知道它在完全二叉树中的parent，left，right，非常容易：PARENT (i) return i/2LEFT (i) return 2iRIGHT (i) return 2i + 1 那么现在对于输入数组，已经抽象为完全二叉树了，那就要开始建堆， 先来学习一个重要的堆操作MAX-HEAPIFY MAX-HEAPIFY (A, i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≤ heap-size[A] and A[l] > A[i] 4 then largest ← l 5 else largest ← i 6 if r ≤ heap-size[A] and A[r] > A[largest] 7 then largest ← r 8 if largest ≠ i 9 then exchange A[i]，A[largest] 10 MAX-HEAPIFY(A, largest) 这个函数就是对数组A中的第i个节点进行heapify操作 其实比较简单，1～7就是比较找出，i节点和左右子节点中，哪个最大 8～10，如果最大的不是i，那就把最大节点的和i节点交换，然后递归对从最大节点位置开始继续进行heapify 显而易见，对于n个节点的完全二叉树，高为lgn，对每个节点的heapify操作是常数级的，所以这个操作的时间复杂度就是lgn 那么有了heapify操作，建堆的算法很简单的，BUILD-MAX-HEAP (A) 1 heap-size[A] ← length[A] 2 for i ← length[A]/2 downto 1 3 do MAX-HEAPIFY(A, i)
说白了，就是对i从length[A]/2到1的节点进行heapify操作。所以这个操作的时间复杂度上限咋一看应该是nlgn，其实比这个小的多，约等于2n，就是说建堆的时间复杂度是O(n)，能够在线性时间内完成，这个是很高效的。 这个算法的依据是the elements in the subarray A[(n/2+1) ‥ n] are all leaves of the tree，所以我们只需要对所有非叶节点进行heapify操作就ok了 折腾半天堆建好了，怎么堆排序了，光从堆是得不到一个有序序列的。HEAPSORT (A) 1 BUILD-MAX-HEAP(A) 2 for i ← length[A] downto 2 3 do exchange A[1]，A[i] 4 heap-size[A] ← heap-size[A] - 1 5 MAX-HEAPIFY(A, 1) 原理很简单，从堆我们只能知道最大的那个，那么就把最大的那个去掉，然后heapify找到第二大的，依次下去。 实现也很巧妙，没有用到额外的存储空间，把堆顶放到堆尾，然后堆size-1 这个算法的时间复杂度也是nlgn
Python版
1 def heapSort(input): 2 output = [] 3 buildHeap(input) 4 print input 5 while input: 6 i = len(input) - 1 7 input[0],input[i] = input[i],input[0] 8 output.append(input.pop()) 9 if input: 10 maxHeapify(input,0) 11 return output 12 13 def maxHeapify(input, i): 14 if i < 0: 15 return 16 left = 2 * i + 1 # because the i from 0, not 1 17 right = 2 * i + 2 18 largest = i 19 length = len(input) 20 if left < length: 21 if input[i] < input[left]: largest = left 22 if right < length: 23 if input[largest] < input[right]: largest = right 24 if largest != i: 25 input[i], input[largest] = input[largest], input[i] 26 maxHeapify(input,largest) 27 28 def buildHeap(input): 29 length = len(input) 30 if length < 2 : return 31 nonLeaf = length / 2 32 for i in range(nonLeaf, - 1 , - 1 ): 33 maxHeapify(input,i)堆排序介绍完了，有什么应用 我看到的在搜索引擎在生成查询结果时，需要对N个候选集进行排序并取前r个作为查询结果，这时r<<N 这时用堆排序比较经济，首先生成堆，然后排序的时候只要做r次heapify，然后后面的就可以不管了，省了很多时间。 书上介绍的典型应用是Priority queues 说了堆排序是个非常好的排序算法，但是在实际应用中了还是输给了快排，所以别人都用快排了。但是heap这个数据结构的应用是很广的。 比如这个典型应用Priority queues queue就是先进先出，那么Priority queues有了priority，复杂一点了，priority大的先出，这个可以用于比如cpu的task，job调度。 这个priority queue用堆实现就很合适了，下面就是定义了需要的一些操作，HEAP-MAXIMUM (A) 1 return A[1]HEAP-EXTRACT-MAX (A) 1 if heap-size[A] < 1 2 then error "heap underflow" 3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5 heap-size[A] ← heap-size[A] - 1 6 MAX-HEAPIFY(A, 1) 7 return maxHEAP-INCREASE-KEY (A, i, key) 1 if key < A[i] 2 then error "new key is smaller than current key" 3 A[i] ← key 4 while i > 1 and A[PARENT(i)] < A[i] 5 do exchange A[i]，A[PARENT(i)] 6 i ← PARENT(i)MAX-HEAP-INSERT (A, key) 1 heap-size[A] ← heap-size[A] + 1 2 A[heap-size[A]] ← -∞ 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
本文章摘自博客园，原文发布日期：2011-07-04
