经典算法巡礼(七) -- 排序之堆排序

一、优先队列

很多时候，我们需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。比如你可能启动了若干个定时器，那么下一次处理定时器事件只需要考虑距离现在时间最近的定时器即可，定时器触发时间无须全部有序，只需要处理优化级最高的定时器即可。

这种情况下，一个合适的数据结构应该支持两种操作：删除最小元素和插入元素。而且这两种操作的效率应该在可接受范围之内。这种数据类型叫优先队列。

二、堆的定义

二叉堆能够很好的实现优先队列的基本操作。在二叉堆中，每个元素都要保证大于等于它的孩子结点。相应的，这些孩子结点同样要大于等于它们的孩子结点，以此类推。当然，这样的二叉堆又称最大堆。与最大堆类似，若每个元素均小于等于它的孩子结点，则称最小堆。之前提到的定时器触发问题，它所适合的数据结构应该为最小堆。

三、二叉堆表示法

二叉堆是完全二叉树，因此可以只用数组来表示二叉堆。具体方法是将二叉树的结点按照层级顺序放入数组中，根结点放在位置1，它的子结点放在位置2和3，而子结点的子结点则放在位置4，5，6，7，以此类推。而事实上，很容易就可以在数组中表示二叉树，即位置k的结点，它的子结点在数组中的位置则为2k和2k+1。

四、堆的操作

在堆的有序化过程中，我们会碰到以下两种情况：

• 当某个结点的优先级上升(或者在堆底中加入一个新的元素)时，我们需要由下至上恢复堆的有序性；
• 当某个结点的优先级下降(比如根结点被替换为一个新的元素)时，我们需要由上至下恢复堆的有序列性。

为了解决以上两个问题，就有了下面将要描述的上浮(swin)和下沉(sink)操作。

由下至上的有序化（上浮）

由于某结点的变化，造成了该结点比它的父结点更大（最大堆情况），从而影响了堆的有序性。比如堆中有新的元素加入堆底，而该新加入元素又比它的父结点更大，则需要将其与它的父结点交换位置，从而恢复它及其父结点的有序性。当然，这个过程会不停重复，直至堆中元素全部有序为止。整个过程就是之前所说的由下至上的上浮过程。具体golang可参考如下：

	func (this *HeapPQ) swim(idx int) {
		for idx > 1 && this.less(idx/2, idx) == true {
			this.exch(idx/2, idx)
			idx /= 2
		}
	}

由上至下的有序化（下沉）

由于某结点的变化，造成了该结点比它的子结点更小（最大堆情况），从而影响了堆的有序性。比如删除堆中根结点的元素，并原先在堆底的元素放置于根结点位置。事实上这就是最大堆中取最大元素的操作。当然，为了保持堆的有序性，则对新的根结点进行下沉操作，若根结点比它的子结点中的任意一个小，则将根结点与此结点交换，同时将该子结点进行重复操作，直到堆恢复有序性为止。整个过程就是之前的说的由上至下的下沉过程。具体golang可参考如下：

	func (this *HeapPQ) sink(idx int) {
		for 2*idx <= this.Size() {
			child := 2 * idx
			if child < this.Size() && this.less(child, child+1) == true {
				child++
			}
			if this.less(idx, child) != true {
				break
			}
			this.exch(idx, child)
			idx = child
		}
	}

五、堆排序

堆排序可以分为两个阶段：

• 堆的构造阶段
• 下沉排序阶段

构造一个堆，可以用以下两种方法进行。第一种，从左至右遍历数组，用swin()保证扫描指针左侧的所有元素已经是一棵堆有序的完全树即可。第二种，事实上是更聪明更高效的方法。就是从右至左用sink()函数构造子堆。开始时我们只需要扫描数组中的一半元素，所以是更高效的方法。

第二个阶段，即下沉排序阶段，我们可以将堆中最大元素删除，然后放入堆缩小后数组空出的位置。

整个过程用代码表述如下：

	func (this *HeapSort) sink(a []Comparable, i int, j int, compare Compare) {
		b := a[i:j]
		b = append(make([]Comparable, 1), b...)
		size := len(b) - 1

		func(idx int) {
			for 2*idx <= size {
				child := 2 * idx
				// fmt.Println(idx, child, size)
				if child < size && compare(b[child], b[child+1]) < 0 {
					child++
				}
				if compare(b[idx], b[child]) < 0 {
					this.exch(b, idx, child)
					idx = child
					continue
				}
				break
			}
		}(1)

		copy(a[i:j], b[1:])
	}

	// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
	func (this *HeapSort) Sort(a []Comparable, compare Compare) {
		n := len(a)

		// 堆构造
		for i := n / 2; i >= 0; i-- {
			this.sink(a, i, n, compare)
		}

		// 堆排序的下沉阶段
		for i := n - 1; i > 1; {
			this.exch(a, 0, i)
			i--
			this.sink(a, 0, i, compare)
		}
	}

至于堆排序的效率，在sink()函数中，比较操作最多进行2logN次，所以排序整个数组最多需要N*2logN次比较操作，因此堆排序的时间复杂度为O(NlogN)，所以可以用于大规模数据的排序。

堆排序是能够同时最优地利用空间和时间的方法，即使在最坏的情况下，它也能保证使用~2NlogN次比较和恒定的额外空间。但现代系统的许多应用很少使用它，因为堆排序无法有效利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序，归并排序，甚至是希尔排序（希尔排序算是没有多少相信元素间的比较的算法了）。

但是，用堆实现优先队列在现代应用程序中却起着重要的作用，因为它能在插入操作和删除最大元素操作保证对数级别的运行时间（logN）。