排序算法——堆排序

2014-01-12

堆排序概述

堆排序通过建立大顶堆(或小顶堆)来进行排序，要理解这个算法，首先要明白什么是 大顶堆 或者 小顶堆 。

这里的堆是一种数据结构，它是一棵完全二叉树(除最后一层外，其他层都是满的)，且每个节点都具有同一种特性，那就是该节点的值大于子节点的值，或者节点的值小于子节点的值，前者被称为 大顶堆 ，后者被称为 小顶堆 。大顶堆的根节点的值一定是整个堆中最大的，小顶堆的根节点的值一定是堆中最小的。利用这个特性，如果要对一个数组进行升序排序，那么可以按照以下步骤进行：

将数组元素视为一个堆，建立大顶堆
将堆顶元素和堆尾元素交换，并出堆
对堆进行处理，维持大顶堆性质
重复2、3步(此时已出堆的元素不再处理)，直到堆中只有一个元素

堆排序实现

首先，要从逻辑上建立对堆的相关操作，在排序中并不需要建立一棵二叉树，而是将数组“视为”二叉树即可。对于二叉树而言，最起码的，应该有取得某个节点的父节点及子节点的功能。

节点访问

用python实现如下：

 1: def parent(heap, node):
 2:     if node > 0:
 3:         return (node - 1) / 2
 4:     else:
 5:         return 0
 6: 
 7: def lchild(node):
 8:     return 2 * node + 1
 9: 
10: def rchild(node):
11:     return 2 * node + 2

建立大顶堆

建立大顶堆要从最后一个具有子节点的节点上开始操作，将当前节点作为一个大顶堆的堆顶，进行堆性质维持的处理。并逐步往前对该节点的兄弟节点、父节点进行同样的操作。

首先需要实现一个堆性质维持处理函数，实现如下：

 1: def heapify(heap, root, size):
 2:     max_index = root
 3:     l = lchild(root)
 4:     r = rchild(root)
 5:     if  l < size and heap[l] > heap[max_index]:
 6:         max_index = l
 7:     elif r < size and heap[r] > heap[max_index]:
 8:         max_index = r
 9: 
10:     if root != max_index:
11:         heap[root], heap[max_index] = heap[max_index], heap[root]
12:         heapify(heap, max_index)
13: 
14:     return None

用python实现如下：

1: def build_heap(heap):
2:     size = len(heap)
3:     last = size / 2 - 1
4:     for cur in range(last, -1, -1):
5:         heapify(heap, cur, size)

实现堆排序

根据堆排序概述中的内容，可以大致将堆排序描述如下：

 1: def hsort(arr):
 2:     size = len(arr)
 3:     last = size - 1
 4:     build_heap(arr)
 5: 
 6:     while size > 1:
 7:         arr[0], arr[last] = arr[last], arr[0]
 8:         last = last - 1
 9:         size = size - 1
10:         heapify(arr, 0, size)
11: 
12:     return None

结合前面实现的parent、lchild、rchild、heapify、build_heap几个函数，就可以实现一个完整的堆排序算法了。

发散：TOP K问题

所谓的 TOP K问题 ，是指在大规模数据处理时常遇到的一类问题，要求在海量数据中找出最大的前K个数。这个问题可以通过建立小顶堆来解决——当然了，为了效率和资源的有效利用，这类问题通常还有整体方面的架构设计等工作需要做，远不是只建立一个小顶堆就能解决的，不过这些本文不作讨论。

通过预先读入K个数据并建立小顶堆后，再逐个读入数据，将新元素和堆顶元素进行比较，如果新元素小于堆顶元素，就丢弃；如果新元素大于堆顶元素，则用新元素替代堆顶元素，并且重新调整堆使之保持小顶堆性质。

这样处理后，总可以保证目前读到的数据中最大的K个在小顶堆中。

当我一开始接触到这个问题时，我幼稚地认为应该使用大顶堆，但实际上是错误的。用大顶堆可以保证堆顶元素是最大，但不能保证堆中元素是前K个最大的数。

我误认为应该使用大顶堆的原因还有一个，那就是忽视了“海量数据”这个情境。

对于小规模的TOP K问题，可以直接将数据进行排序，然后取出最大的K个数。但海量数据处理中，数据是不可能同时全部进入内存的。

ZMonster's Blog 巧者劳而智者忧，无能者无所求，饱食而遨游，泛若不系之舟