标签归档:堆排序

优先队列与堆排序

队列(Queues)是应用中常见的数据结构,一个队列至少有“入队”和“出队”两个基本操作。队列具有“先入先出(First In First Out, FIFO)”性质,就像排队一样,入队会将新元素插入到队列的末尾,而出队会取出队列中排在最前的(也是最早入队的)一个元素。

优先队列(Priority Queues)的接口与基本队列一样,至少有“入队”和“出队”两个基本操作。与基本队列不同的是,优先队列的出队顺序不是先入先出,而是以队列中元素的健作为优先级出队,键最大(或最小)的元素最先出队,其次是键次大(或次小)的元素。键大优先出队的优先队列称为面向大元素的优先队列;键小优先出队的优先队列称为面向小元素的优先队列。为了方便,在没有特别说明的情况下,下文所有提到的优先队列均指面向大元素的优先队列。

要实现一个高效的优先队列并不十分容易,一个直观而简易的实现方式是使用有序链表。设 L 是一个按从大到小顺序排列的链表,使用这个链表充当优先队列。当有一个元素 N 需要入队时,只需从头到尾遍历队列,找到插入 N 之后不会破坏链表有序性的位置,将 N 插入链表;当需要出队一个元素时,因为链表的有序性保证了第一个元素一定是最大的元素,因此只需直接取出链表中第一个元素返回,并删除这个元素。

使用链表构建的优先队列入队效率比较低,假设队列长度是 n 那么入队平均需要遍历 n / 2 个结点;而它的出队效率又非常高,显然,它出队的时间复杂度是常数 1。造成链表优先队列入队效率底的根本原因是搜索的效率低,在一个有序的数据结构中逐个元素顺序搜索是不明智的。以往的经验告诉我们,在有序的数据集合中进行查找,高效的做法是用二分的思想。而链表不支持随机访问,在数组中运用的二分法查找在链表中是无效的。

实现优先队列,另一个更聪明的办法是用二叉树来组织数据。维护一棵始终满足以下条件的二叉树,就能实现一个较高效的优先队列:

  1. 是一棵完全二叉树;
  2. 每个结点的键都比它的非空子结点的键大。

通常的二叉树是以链式结构组织的,树各个结点的物理存储位置是离散的,每个结点通过保存该结点的两个子结点以及父结点的引用(或“指针”)来彼此关联。而为了实现优先队列,我们按从上到下、从左到右的顺序将一棵二叉树组织到数组里,所有结点都在数组中连续存放,形成一个二叉堆。按习惯,二叉堆又简称“”,下文也遵循习惯使用简称“堆”指二叉堆。之所以用堆的形式来组织优先队列而不是通常的链式结构,是因为堆能更快更容易地实现优先队列入队和出队的操作,具体的理由总结如下:

  1. 完全二叉树除了底部外所有结点的子结点全都非空,且生长点只能在树的底部,用数组来存放它既没有空位,又无需在插入之后移动元素;
  2. 数组支持随机访问,访问效率优于链式结构的二叉树;
  3. 无需每个结点都保存其子结点或父结点的引用,只需对自身的索引进行简单的运算即可找到子结点或父结点;
  4. 插入新元素时,能非常容易地找到插入点。

假设用数组 a[] 来组织上面说到的堆,为了方便,元素 a[0] 置空不用,从 a[1] 开始存放堆的所有元素。这样,堆的根结点即是 a[1],假设存在某个结点 a[n] (n > 1),那么它的父结点就是 a[n / 2],它的左子结点是 a[2 * n],它的右子结点是 a[2 * n + 1]。

实现对优先队列的入队就是当向堆插入一个元素,先将新的元素插入到堆的尾部成为一个新结点。此时,这个结点很可能并不比它的父结点小,因此堆的性质之一“每个结点的键都比它的非空子结点的键大”可能会遭到破坏,必须做一些处理使堆重新满足这个条件。

这些处理称为结点的“上浮”。结点上浮的目的是将新插入的结点移动到合适的位置,使这个结点既大于它所有的子结点,又小于它的父结点。结点上浮的操作算法很简单:比较被上浮的结点与它的父结点的大小,如果当前结点大于父结点,则交换它们的位置;然后重复上述操作,直到当前结点不大于父结点或者当前结点已经是根结点。下面的 Java 代码实现了堆结点上浮的操作。

实现对优先队列的出队就是读出堆顶部的结点,然后删除它。删除一般二叉树的一个结点,就有可能留下两个孤立的子树,此时需要在树中删出一个没有非空子结点或只有一个非空子结点的结点来填补到删除结点后产生的空缺中。删除堆顶的一个结点,同样需要找一个结点来填补空缺,最容易的办法是删出堆底的结点,填补到堆顶空缺的位置,然后堆大小减 1。这时填补到堆顶的结点几乎一定是会比它的左右子结点都小的,不满足优先队列堆要求的条件,需要做一些处理使堆重新满足条件。

这些处理称为结点的“下沉”。结点下沉的目的是将处于堆顶部的小结点向堆底移动,使这个结点既大于它所有的非空子结点,又小于它的父结点。像结点的上浮操作一样,结点的下沉操作也很容易实现。先从结点的左右子结点中找出非空且较大的那一个,被下沉的结点与之交换,重复这个过程,直到当前结点大于它的所有非空子结点或者它的所有子结点均为空。下面的 Java 代码实现了堆结点的下沉操作。

如果将一串乱序数据全部入队到一个优先队列中,然后从优先队列中出队所有的数据,数据出队时将是有序的,这无疑提供了一个新的排序思路。

堆排序就是利用了上述优先队列思想的排序算法。对一个乱序的数组进行堆排序时,分为两个阶段,第一阶段称为建堆,将数组原地组织成一个符合上文中描述的条件的堆;另一个阶段把这个堆当作优先队列,不断地出队元素,并把出队的元素填到因出队而空缺的位置。当堆逐步缩小直至为空时,堆排序完成,数组变成了有序数组。

如何对一个数组实现原地建堆是一个值得思考的问题,为了讨论问题方便,先定义“堆有序”指一个堆满足上文提到的优先队列堆的所有条件。显然,一个大小为 1 的堆一定是堆有序的。如果一个堆 H 的左右两个子堆都是堆有序的,只要对这个堆的根结点做一次下沉操作,堆 H 也一定会转化为一个堆有序的堆。设有一个乱序数组 a[1…n],把它看作一个堆,Hi 表示以 a[i] 为堆顶的子堆,则可以得出 Hn/2+1, Hn/2+2, …, Hn 均是大小为 1 的子堆,换言之,这些子堆都是堆有序的,数组 a 中有半数子堆是堆有序的。为了使整个数组都成为堆有序的堆,只要先后对 a[n/2], a[n/2-1], …, a[1] 执行下沉操作即可。

建堆完成后,就可以开始第二步骤了。将数组当作一个优先队列,出队一个元素 N1,此时 a[n] 处因出队产生了一个空缺,将 N1 填补到 a[n] 处,继续出队 N2,填补到 a[n-1] 处,直到出队 Nn,填补到a[1] 处,数组 a 排序完成。

值得注意的是,在实际运用中,大部分程序设计语言的数组第一个元素的索引并不是 1 而是 0,但只要在上述算法的基础上对索引稍作处理即可实现堆排序。

堆排序无需额外的空间,时间复杂度也能达到比较理想的 O(nlogn) 的级别,是一种优秀的排序算法。

本文提到的全部算法均已用 Java 实现,代码托管于 GitHub,查看

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=250 )