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

排序算法——堆排序

堆排序概述

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

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

  1. 将数组元素视为一个堆,建立大顶堆
  2. 将堆顶元素和堆尾元素交换,并出堆
  3. 对堆进行处理,维持大顶堆性质
  4. 重复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个数。但海量数据处理中,数据是不可能同时全部进入内存的。