`
bencode
  • 浏览: 106909 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

《算法导论》读书笔记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时也等了好久:) 不过可以对计算结果进行适当的缓存,就可很大提高计算的速度:)

 

  • 大小: 4.6 KB
  • 大小: 6.2 KB
  • 大小: 8.5 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics