《算法导论的Java实现》 7 堆排序

7 堆排序

7.1 堆

堆的概念不想多介绍，书上都有。这里只提几个基本概念，以说明后面的伪代码。
堆可以看出一颗完全二叉树，除了最后一层，树的每一层都是填满的，最后一层，也是从左至右填。
在堆排序里面，堆就用数组表示，不需要其他的数据结构（因为是完全二叉树），观察后面伪代码，可以看出，对于完全二叉树，用3个函数（用C来实现的话是3个宏（macro）），可以确定任何一个节点的父子节点。
想强调的是，这里没有一个叫“堆”的数据结构，它只是个数组，堆（完全二叉树）存在于我们的脑子了，我们用本篇后面介绍的很多方法来操作这个很普通的数组，所有的方法的集合，就赋予了这个普通的数组以“堆”的属性。
类似的，如果有个双向链表（数组也可以），我们赋予它先进先出的存取方法集合，那么它就是个“队列”；如果我们赋予它先进后出的存取方法集合，那么它就是个“栈”。队列和栈本身没有与众不同的实体，它们只是普通的链表（或者数组），队列和栈是存在于我们脑子中的。所谓“运用之妙，存乎一心”（《宋史·岳飞传》）就在于此。


伪代码：

PARENT(i) return ┕i/2┙LEFT(i) return 2iRIGHT(i) return 2i + 1

Java代码：

public static int parent(int i) { return (i - 1) >> 1; } public static int left(int i) { return ((i + 1) << 1) - 1; } public static int right(int i) { return (i + 1) << 1; } public static void main(String[] args) { for (int i = 0; i < 10; i++) { System.out.print(parent(i) + " "); System.out.print(left(i) + " "); System.out.println(right(i) + " "); } }

   
输出：
-1 1 2
0 3 4
0 5 6
1 7 8
1 9 10
2 11 12
2 13 14
3 15 16
3 17 18
4 19 20

上面输出的是对于每个节点（0到9）的父节点，左子节点，右子节点的数组下标。
根节点0的父节点是-1（伪代码里面是0）。
要说明的是：伪代码里面的乘2除2运算，我在Java里面都用了位移操作。这更符合堆排序的本意。在C和汇编里，位移运算比乘除要快得多。位移运算比加减更快，可能只占一个CPU时钟，乘除要占20多个以上，差了一个数量级。效率而言，那是差不起的。

7.2 保持堆的性质

伪代码：
MAX-HEAPIFY(A, i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≤ heap-size[A] and A[l] > A[i] 4 then largest ← l 5 else largest ← i 6 if r ≤ heap-size[A] and A[r] > A[largest] 7 then largest ← r 8 if largest ≠ i 9 then exchange A[i] ←→ A[largest]10 MAX-HEAPIFY(A, largest)

Java代码：
public static <T> void heapify(T[] a, int i, Comparator<? super T> c) { int l = left(i); int r = right(i); int next = i; if (l < a.length && c.compare(a[l], a[i]) > 0) next = l; if (r < a.length && c.compare(a[r], a[next]) > 0) next = r; if (i == next) return; swap(a, i, next); heapify(a, next, c); } private static void swap(Object[] arr, int i, int j) { Object tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /** * @param args */ public static void main(String[] args) { //heapify test Integer[] temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 }; heapify(temp, 1, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); for (int i : temp) { System.out.print(i + " "); } System.out.println(); }
  
输出：
5 6 4 6 1 3 2 2

这里如果不说明一下，可能有点理解困难，因为我的文章里面没有图，二叉树的图像必须存在于自己的脑子里。如果参考了《算法导论》里，这个章节的堆的二叉树图像的话，将容易理解得多。
我这个测试代码里，输入的是：5, 2, 4, 6, 1, 3, 2, 6
它的图像如下：

                5
         2            4
      6     1      3     2
    6

如果，你还没有理解堆是怎么一回事儿，那就就把上面这个二叉树，从上到下，从左到右，遍历一遍，别去管树的父子关系。从上到下，从左到右，遍历的结果，就是原来的输入：5, 2, 4, 6, 1, 3, 2, 6。也就是我前面说过的，数组还是那个数组，但是“存乎一心”的去想象，在脑子里，把数组的元素一个一个抽出，放到二叉树里面，第一行放一个（根），第二行放2个，第三行放4个，……，第n行放2^(n-1)个，放完为止，最下面一行，右面部分可以为空，别的地方都应该是满的，这就是堆（完全二叉树）。
然后，测试时，调用heapify函数，参数是1，也就是说对第二个元素进行重排，也就是上面二叉树图像里面第二行最左面的元素“2”进行重排。heapify里面，会把“2”和它的左右节点“6”和“1”进行比较，得出左节点“6”最大（比自己和右节点大）。就把自己（“2”）和左节点“6”进行交换，然后递归左节点（第4个元素，下标为3）。交换以后，原来的左节点（第4个元素，下标为3）的值是本身“2”，再一次（递归）判断自己和左右节点的关系，由于没有右节点，就只需要和左节点，最下层那个孤零零的“6”进行比较，然后交换。最后得出的图像如下：

                5
         6            4
      6     1      3     2
    2

上面的图像还原成数组，也就是我的程序的输出结果：5 6 4 6 1 3 2 2

堆排序里面，上面这个函数是最核心部分，它非常的漂亮（自我感觉Java程序比伪代码更加漂亮，呵呵），所以整个堆排序也是非常漂亮的一种排序。


7.3 建堆

伪代码：
BUILD-MAX-HEAP(A)1 heap-size[A] ← length[A]2 for i ← ┕length[A]/2┙ downto 13 do MAX-HEAPIFY(A, i)

Java代码：
public static <T> void buildHeap(T[] a, Comparator<? super T> c) { for (int i = (a.length + 1) / 2 - 1; i >= 0; i--) { heapify(a, i, c); } } /** * @param args */ public static void main(String[] args) { //buildHeap test Integer[] temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 }; buildHeap(temp, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); for (int i : temp) { System.out.print(i + " "); } System.out.println(); }
   

输出：
6 6 4 5 1 3 2 2

有了前面的基础，把这个输出想象成一个二叉树，应该不太困难了：

                6
         6            4
      5     1      3     2
    2

上面就是一个建好的堆，它满足每个节点都比自己的子节点要大。
稍微要说明一下的是：for i ← ┕length[A]/2┙ downto 1
为什么从┕length[A]/2┙开始？因为我们不用重排叶子节点。
我的测试数组中，一共8个元素，也就是只要从第4个元素开始循环就可以了。大家可以验证一下，第4个元素也就是第3行的第一个元素，最后的结果是“5”的那个节点，它是最后一个有儿子的节点，从它往后，都是叶子节点了。为什么只要除以二再向下取整，为什么会如此简洁？一切的起因就是：它是一颗二叉树，每一层的个数是2^(n-1)，全满的时候，总数是2^n个。


7.4 堆排序算法

伪代码：
HEAPSORT(A)1 BUILD-MAX-HEAP(A)2 for i ← length[A] downto 23 do exchange A[1] ←→ A[i]4 heap-size[A] ← heap-size[A] - 15 MAX-HEAPIFY(A, 1)

对已经建立好的堆，运行上面的伪代码后，就可以得到，排好顺序的数组了。
但是，直接看上面的伪代码，并不是很容易理解，那就要仔细看一下《算法导论》的原文了。
我这里简单介绍一下思路：第一次建立好堆之后，第一个元素（根）就是我们要的排好序的第一个元素；把这个元素和最后一个元素进行交换（也就是抽出），然后调用HEAPIFY函数，进行重组堆。
这里要注意：重组堆重组所有的数组元素，而是重组从第一元素开始到没有被抽出的元素为止。这里要用到伪代码的heap-size[A],它看上去像一个函数，但其实它只是个变量。之所以，我前面的Java实现都没有管这个变量，那是因为一直没有用到，建堆时，是把整个数组都当成一个堆的，不需把后面若干元素排除在外。
现在，我们需要这个heap-size[A]变量了，它为我们指出，当前堆的最后一个元素，而这个元素之后的都是已经被抽出，已经排序好的元素。
下面的Java实现里，会重载（overload）heapify这个函数，没有搞清什么叫重载（overload），什么叫重写（override）和多态（polymorphism）的，要自己回家好好看书。

Java代码：

import java.util.Comparator;public class HeapSort { public static int parent(int i) { return (i - 1) >> 1; } public static int left(int i) { return ((i + 1) << 1) - 1; } public static int right(int i) { return (i + 1) << 1; } private static void swap(Object[] arr, int i, int j) { Object tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static <T> void heapify(T[] a, int i, Comparator<? super T> c, int size) { int l = left(i); int r = right(i); int next = i; if (l < size && c.compare(a[l], a[i]) > 0) next = l; if (r < size && c.compare(a[r], a[next]) > 0) next = r; if (i == next) return; swap(a, i, next); heapify(a, next, c, size); } public static <T> void heapify(T[] a, int i, Comparator<? super T> c) { heapify(a, i, c, a.length); } public static <T> void buildHeap(T[] a, Comparator<? super T> c) { for (int i = (a.length + 1) / 2 - 1; i >= 0; i--) { heapify(a, i, c); } } public static <T> void heapSort(T[] a, Comparator<? super T> c) { buildHeap(a, c); for (int i = a.length - 1; i > 0; i--) { swap(a, 0, i); heapify(a, 0, c, i); } } public static void main(String[] args) { //heapSort test Integer[] temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 }; heapSort(temp, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); for (int i : temp) { System.out.print(i + " "); } System.out.println(); }}

输出：
1 2 2 3 4 5 6 6

前面，我给出的都是和伪代码相对应的Java代码片段。而直到这里，我把所有的代码都给出了，因为我们的堆排序已经完成了。

coding后感
这次的感想不多，因为很多要说的，在上面各段伪代码说明时都说了。
之所以针对每段伪代码都做了说明，是因为堆排序不如别的排序（插入，选择，冒泡）那么直观，需要动脑筋想象二叉树。
数组下标的差异，在堆排序里，没有造成太大的困扰，甚至于，因为Java数组下标从零开始，反而使Java的代码更加的漂亮。
堆排序的程序量其实不多，但是heapify，buildHeap，heapSort这3个函数各司其职，配合的丝丝入扣。

7.5 优先级队列

伪代码：

HEAP-EXTRACT-MAX(A)1 if heap-size[A] < 12 then error "heap underflow"3 max ← A[1]4 A[1] ← A[heap-size[A]]5 heap-size[A] ← heap-size[A] - 16 MAX-HEAPIFY(A, 1)7 return max

伪代码：

HEAP-INCREASE-KEY(A, i, key)1 if key < A[i]2 then error "new key is smaller than current key"3 A[i] ← key4 while i > 1 and A[PARENT(i)] < A[i]5 do exchange A[i] ↔ A[PARENT(i)]6 i ← PARENT(i)

MAX-HEAP-INSERT(A, key)1 heap-size[A] ← heap-size[A] + 12 A[heap-size[A]] ← -∞3 HEAP-INCREASE-KEY(A, heap-size[A], key)

code后感
上面的伪代码，我写了一点点就放弃了，所以没有Java代码提供给大家。因为实在没有太大的意思。

优先级队列是一个堆的应用，堆排序完成后，原来的代码上增加堆的追加和删除操作后，可以形成一个实用的优先级队列。大学三年级时，学操作系统时，我们都做过作业，自己做个小型的分时系统，进程调度管理，我本来准备参考windows的，因为linux的程序是公开，同学大多抄袭linux代码，而我想干点有难度的，就去反编译windows。后来发现，就内核而言，windows95根本就不是个多进程系统。到后来，我才知道，原来当然微软正从DOS的单进程往windows的多进程进发，而其主程序员实在太蹩脚，根本不懂多进程，所以windows95的多进程完全是个假的。当时，如果我知道有这个优先级队列的话，就不会去跟踪windows的内核了，也可以节约很多时间。
说到微软的蹩脚程序员，不得不说我当年学VC的经历。我学的时候VC还是4.0，后来做毕业设计的时候是6.0。和现在学Java一样，我花了很多时间去研究MFC的源代码，后来发现VC4.0的CD里面有个目录，里面的C/C++代码，非常的优美，让人赏心悦目；而其他的地方，写得还不如俺的一些同学。后来有人告诉我，我看的实际上是HP的代码，他们帮微软在做事儿。后来的VC6.0已经把HP的代码买下来，融入自己的了。不过就算如此，我还是发现，VC6.0的伪随机函数是错的。我曾直接联系他们的总部，报告random这个bug。98年的时候，我虽然已经开始用Internet好几年了，但是没有email，他们的态度倒是挺好，直接从西雅图邮国际信件给俺，说知道这个bug了，会处理的。不过后来，俺毕业后，开始的工作是汇编，然后是Java，再也没有碰过微软的东西，不知道他们bug是不是还是那么多，内部的source还是那么烂。