《算法导论》读书笔记3(堆排序)

第二部分，排序和顺序统计学

 

在笔记一中， 我们实现了两个排序算法：插入排序和归并排序。

 

第六章是堆排序。现在就是第六章。

 

这里的堆，不是堆栈的堆，那个一般是指一块动态分配的内存：）

 

这里的堆是一个数据结构，它是一个二叉树（二叉堆），可以存在数组中

 

像这样：

 

           16
         /     \
      14        10
    /    \     /    \
  8       7   9      3      ->   16 14 10 8 7 9 3 2 4 1
 / \     /
2   4   1

 

根要比左右两个结点要大，并且左右子树也是一个堆--> 是一个递归定义

 

可以用这样的代码来表示上述定义

 

	boolean isHeap(int[] a, int i) {
		int n = a.length;
		if (i >= n) {
			return true;
		}
		int left = 2 * i + 1;    // 左节点
		int right = 2 * i + 2;   // 右节点
		if (left < n && a[left] > a[i]) {	// 比左右都要大，否则不行
			return false;
		}
		
		if (right < n && a[right] > a[i]) {
			return false;
		}
		
		return isHeap(a, left) && isHeap(a, right);   // 左右子树也是堆
	}

 

然后写一个测试运行一下：

 

	@Test
	public void testIsHeap() {
		int[] a = { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };  // 就是上述图示数据
		assertTrue(isHeap(a, 0));
	}

 

显然， 根节点就是最大的。那么堆排序就是基于这个特性：每次选出"最大的", 再建，再选， 直到排好：）

 

算法像这样：

 

	void heapSort(int[] a) {
		buildHeap(a);  // 首先，建一个堆， 此时a[0] 就是最大的元素
		for (int i = a.length - 1; i  > 0; i--) { // 每次"选出"最大的元素， 共需要进行 n - 1 次
			swap(a, 0, i);	//  在这之后， i 以及后面的元素都是有序的
			heapify(a, 0, i - 1);   // 根元素由于被交换过，所以需要进行一次“调整”, 
                                                                                //  让他再变成堆
		}
	}

 

 算法很简单， 但是编译还是不通过的：） 因为有三个方法还没有完成。

 

swap：交换数组元素， 这个很容易，属于"模板代码" (PS:晚上喝了好些杨梅酒， 希望不要错)

 

	void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

 

 

再来 heapify, 这个比较容易些：）

 

	 // 此时 i 的左右子树都是堆 (j 后面的元素不管，不属于堆), 我们要把他调整成堆

	void heapify(int[] a, int i, int j) { 
		int left = i * 2 + 1;
		int right = i * 2 + 2;
		if (left >  j) {	// 没有左子树？ 那就好了
			return;
		}
		
		int large = left;        // large 是大的这个
		if (right <= j && a[left] < a[right]) {
			large = right;
		}
		
		if (a[i] < a[large]) {    // 根元素比 large  小？ 交换根和 large
			swap(a, i, large);  
			heapify(a, large, j); 此时 large 树 又可能不是堆了, 那就继续努力:)
		}
	}

 

 

 建堆是这样滴

 

 

 

	void buildHeap(int[] a) {
		int n = a.length;
		for (int i = n / 2 - 1; i >= 0; --i) { // n / 2 - 1, 就是最后一个有子节点的元素
			heapify(a, i, n - 1);      // 偶们从这开始，不断调整，直到整个数组变成堆
		}
	}

 

 

现在完工了， 然后再写一个测试代码测试它---证明比较累， 无情的测试相对容易些

 

可以测试空数组，一个元素，两个元素， 一万个元素的随机数组， 测试一万次。 都green, 就米问题了：）

 

 

	@Test
	public void testHeapSort() {
		for (int i = 0; i < 10000; i++) {
			int[] array = genRandAry(i);
			heapSort(array);
			assertTrue(isSorted(array));
		}
	}

 

以上 genRandAry 以及 isSorted ， 见“算法笔记1”

 

程序要跑起来，算法要写出来。。否则变成纯思维，很纠结

 

 

 

照惯例，要看看算法的复杂度。对于排序而言， 就是看看比较次数，因为排序的主要操作就是比较（这里的排序是基于比较的）

 

下面，我们要修改heapSort, 现在不是排序，而是求heapSort的比较次数

 

由于heapify是基本操作， 先来分析它:)

 

目标是，要把下面方法重构成 计算比较次数

 

 

	void heapify(int[] a, int i, int j) {
		int left = i * 2 + 1;
		int right = i * 2 + 2;
		if (left >  j) { 
			return;
		}
		
		int large = left;
		if (right <= j && a[left] < a[right]) {   // 这里是一次元素比较
			large = right;
		}
		
		if (a[i] < a[large]) {    // 这里又是一次比较
			swap(a, i, large);   //   这个不管它
			heapify(a, large, j);   // 这个？ 递归调用而已
		}
	}

 

所以,   上面的方法可以重构成这样

 

	int heapify2(int[] a, int i, int j) {	// modify the return type to int
		int left = i * 2 + 1;
		int right = i * 2 + 2;
		if (left >  j) {
			return 0;	// 没有子树，比较次数为0
		}
		
		int times = 2;	// added
		
		int large = left;
		if (right <= j && a[left] < a[right]) {
			large = right;
		}
		
		
		if (a[i] < a[large]) {
			swap(a, i, large);
			times += heapify2(a, large, j);	// modified
		}
		
		return times; // added
	}

 

下面要删掉无关的代码,  large 就是 left（因为和排序没关系） ，left 就是 i * 2 + 1

 

所以:

 

	int heapify2(int[] a, int i, int j) {
//		int left = i * 2 + 1;
//		int right = i * 2 + 2;
		if (i * 2 + 1 >  j) {
			return 0;
		}
		
		int times = 2;
		
		int large = i * 2 + 1;
//		if (right <= j && a[left] < a[right]) {
//			large = right;
//		}
		
		
//		if (a[i] < a[large]) {
//			swap(a, i, large);
			times += heapify2(a, large, j);
//		}
		
		return times; // added
	}
}

 

 

整理一下：

 

	int heapify2(int[] a, int i, int j) {
		if (i * 2 + 1 >  j) {
			return 0;
		}

		return 2 + heapify2(a, i * 2 + 1, j);
	}

 

和 a 无关

 

	int heapify2(int i, int j) {
		if (i * 2 + 1 >  j) {
			return 0;
		}
		return 2 + heapify2(i * 2 + 1, j);
	}

 

比较容易看出，以上heapify2可以优化为迭代版本， 预示着heapify 代码也可以使用迭代 代替 递归。

 

 

如果对n个数进行调整，此时 i  = 0, j = n

 

	int heapifyN(int n) {
		return heapify2(0, n);
	}

 

 

在算法笔记二中，我们有一个工具可以用来看看复杂度，现在试一下:)

 

往charts目录中加一个文件： HeapifyN.rb

 

module Charts
  class HeapifyN
    def name
      'heapfy(n)'
    end
    
    def fun(x)
      return nil unless x >= 0
      x = x.to_i
      heapfy(0, x);
    end
    
    def heapfy(i, j)
      if i * 2 + 1 > j
        return 0
      end
      
      return 2 + heapfy(i * 2 + 1, j)
    end
  end
end

 

运行，就能绘出如下图

 

 

 

绿的就是 heapify(n) , 蓝的是 log(x)  黄的是 log10(x) 

 

所以 它的复杂度和 log(n) 相当的

 

 

下面是buildHeap, 它的代码是这样的：

 

	void buildHeap(int[] a) {
		int n = a.length;
		for (int i = n / 2 - 1; i >= 0; --i) {
			heapify(a, i, n - 1);
		}
	}

 

重构成求比较次数，差不多是这样：

 

	int buildHeap2(int n) {
		int times = 0;
		for (int i = 0; i < n / 2; i++) {
			times += heapify2(i, n - 1);
		}
		return times;
	}

 

 

OK,   这个复杂度不会大于 nlog(n)， 因为heapify2 是 log(n), 循环了 n / 2 次, 但是 是否为 nlog(n)呢？(因为有一半元素不需要 heaify, 而且每次heapify 的规模也不一样)

 

我们再来画画图：）

 

 

 

蓝线是 nlog(n), 黑线是 buildHeap。

 

书中经过数学推导，证明其复杂度是 O(n)， 图中黑线很“直”，所以应该是线性的

 

还有最后一个heapSort， 这个是多少呢？ 不过肯定比 buildHeap 要大，因为一开始就要buildHeap.

 

然后还要进行 n-1次heapify。

 

还是再画图吧:)

 

 

 

其实画buildHeap时就比较累了， 当横坐标为2000时，等了好几秒。 现在 heapSort 就更慢了， 横坐标为1000时也等了好久：） 不过可以对计算结果进行适当的缓存，就可很大提高计算的速度：）