【数据结构】之堆排序

本文从以下几个方面阐述堆排序：

1 何谓“堆”？

2 完全二叉树的特点

3 堆排序如何实现？

4 树的存储

5 PriorityQueue内部如何实现堆排序？

6 总结。

 

 

1 何谓“堆”？

  一个序列满足以下定义，我们把它称作“堆”：

  a）以完全二叉树的结构存储 ;b)所有非终端节点的值均不大于或者不小于其左右孩子节点的值。

注意：此处用的是“不大于或者不小于”，说明节点等于它的左或右孩子也是可以的。“不大于”时为小顶堆，“不小于”时为大顶堆。

 

 

   如图：
 
 

 注意：大顶堆的堆顶元素并不一定是最大的。只要满足了上述情况即可以成为“堆”。要使堆顶元素最大或者最小，则需要用到堆排序，完成的就是每次得到最大（或者最小）堆顶元素并输出得到有序序列的过程。

 

 2 完全二叉树

从上面对“堆”的定义可知：堆首先是一棵完全二叉树，那么在分析堆排序之前我们有必要先来了解以下什么是完全二叉树：

 

定义：深度为k,有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1~n的节点一一对应，这样的树称为完全二叉树。（此处不详谈，对此不理解的读者请自己百度之）

 

完全二叉树的特点：

 1）叶子节点只可能在层次最大的两层上出现。

 2）当右分支下的子的最大层次为L时，左分支下的子孙的最大层必为L或者L+1。

 

完全二叉树的性质：

1）具有n个节点的完全二叉树的深度为[logN]+1.

2) 节点从1~n,若节点i>1,则双亲是节点[i/2](取整)；若2i>n,则无左孩子，否则左孩子为2i;若2i+1>n,则无右孩子，否则右孩子为2i+1.

 

3 堆排序如何实现？

 

步骤：a)初始建堆：即由一个无序序列建立一个堆。b)筛选重新建堆，保证每次得到的堆顶元素为最大或者最小，输出堆顶元素，重复操作，得到有序序列。

 

首先我们来看如何筛选建堆？假设现在已经有一个建立好的小顶堆，输出堆顶元素后,我们如何把剩余的元素重新建一个堆，使得堆顶元素最小呢？

 

看图：

 方法如下：输出13后，把最后一个元素80换到堆顶位置，因为80>27,则又需交换27与80的位置，又发现80>65,因此又需交换80与65的位置，最后得到：

 此即为输出13之后对剩余元素的重新筛选建立堆。

 

现在再让我们回到前面，我们如何从一个无序序列得到初始的小顶堆呢？其实初始建堆就是把上述过程反复的执行。首先把无序序列构造为一棵完全二叉树，从下往上比较每一个节点与其双亲节点，小的值上移，如此遍历完整棵树，则得到了一个初始的小顶堆。

 

注：笔者表达能力有限，对此不清楚的读者请翻看数据结构书......

 

 

4 树的存储。

   了解了堆排序的原理后，这样的过程如何在代码中实现呢？我们先得知道树的存储结构：

  1）双亲表示法。即数组存储。用一组连续的空间存放树的节点，每个节点中设一个指示器指向双亲节点在数组中的位置。

      优劣：找双亲容易，但要找某一个节点的儿子则需要遍历整个数组。

  2）孩子表示法：即数组与链表结合存储。每个节点放在顺序存储的结构中，每个节点中又包括一个指向其孩子的指针。大概形式如下图：

 3）孩子兄弟表示法：即链表存储。（此处详情略）

 

5 PriorityQueue内部如何实现堆排序：

   此处在我的另外一篇博客http://792881908-qq-com.iteye.com/blog/1454401 中有解析。

 

6 总结：

  堆排序是一种在树形选择排序上的优化，有它一定的优势，但在记录较少的文件中并不提倡，对于它和其他排序方式性能的比较还有待进一步分析。