Heap sort 堆排序

堆排序可以分为构造堆和排序输出两个阶段。在构造堆的过程中，将原始数组重新组织安排进一个堆中， 然后从这个堆中依次输出最大或最小元素，即可得到排序结果。

构造堆

构造堆有由上自下和由下自上两种构造方法。由下自上的构造主要用于以下情况， 即堆的有序状态被破坏是因为某个结点变得比它的父节点要大时，此时就要交换当前结点与其父节点。 由上自下的构造则是用于以下情况，堆的有序状态被破坏是因为某个结点变得比他的子节点小的情况下， 此时需要将它与它的较大的子节点交换（之所以选较大的，是因为该结点要成为新的父节点， 所以不能随便选，要选择那个较大的）。

public static void HeapSort(List<Integer> list) {
	int len = list.size() - 1;
	// construct the big head heap
	for (int k = len / 2; k > 0; k--){
		sink(list, k, len);
	}
	int to_be_outputted_len = len;
	while (to_be_outputted_len > 1) {
		exchange(list, 1, to_be_outputted_len--); // output current root
		sink(list, 1, to_be_outputted_len); // sink the new root to where it fits
	}
}

private static void sink(List<Integer> list, int k, int n) {
	while (2*k <= n) {
		int i = 2 * k;
		if (i < n && less(list, i, i + 1)){ // find the bigger child node
			i++;
		}
		if (!less(list, k, i)){ // already reach where it fits
			break;
		}
		exchange(list, i, k);
		k = i;
	}
}

为了能够简单方便的计算堆的子结点（2i，2i+1）和其父节点（i/2），在测试数据中， 第0位就不会使用了，而是直接从第一位开始。所以在第一个for循环中，k是从第一个有孩子的节点开始。 k的退出条件就是k>0，即最后一个处理的元素是索引为1的元素，它将下沉到它应该位于的位置中。 在排序时while中，退出条件则是len > 1，即最后交换的是倒数第二个元素和它前面的元素， 即倒数第一个元素。之所以与上面的for中不一样，是因为for中是当前元素在与其后面的元素比较、交换， 而在while中，则是当前元素与其前面的元素比较、交换。
在sink中，由于是大元素下沉，所以while的判断条件是当前元素的子元素2*k是否超过此次下沉的边界。 同样的，循环条件的改变也就是k不断地通过k=i扩大。需要额外注意的是内部寻找较大孩子节点时， 一定要判断下i与n的大小关系，否则在比较大小时i+1就会越界。第二个if用来判断是否还需要继续循环， 若当前节点已经大于其子元素，那么就不需要继续循环，直接退出即可。

关于堆

通过一段时间的复习，我似乎渐渐明白为啥java用堆来管理内存了。首先堆是一种特殊的树， 它满足这样的条件：

该树的每一个节点都大于（小于）等于它的任意子节点。

堆是一种很高效的数据结构。为什么说它高效呢，我们都知道数组与链表的优劣， 数组访问很快，但是插入删除很慢；链表是插入删除很快，但是访问很慢；那么， 有没有折中的方案呢？堆就是这个折中的方案。因为它的有序性，它的访问要快过链表； 又因为它本身是链表结构的，所以它的插入和删除又比数组要快， 而且不需要大量的移动元素。我觉得这可能就是java虚拟机使用堆来管理内存的原因吧。