就地堆排序

本文最先发布在我的个人博客[url]http://www.lovestblog.cn[/url]。
今天来了解一下堆排序的问题，“堆”是个很有趣的结构。通常“堆”是通过数组来实现的，这样可以利用数组的特点快速定位指定索引的元素。而对“堆”的操作中定位某个元素简直就是家常便饭。为什么这么说呢，我们来看看“堆”的定义：

在起始索引为 0 的“堆”中：
1) 堆的根节点将存放在位置 0
2) 节点 i 的左子节点在位置 2 * i + 1
3) 节点 i 的右子节点在位置 2 * i + 2
4) 节点 i 的父节点在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作

在起始索引为 1 的“堆”中：
1) 堆的根节点将存放在位置 1
2) 节点 i 的左子节点在位置 2 * i
3) 节点 i 的右子节点在位置 2 * i + 1
4) 节点 i 的父节点在位置 floor( i / 2 ) : 注 floor 表示“取整”操作

以下是一个“堆”的图例：
[img]/upload/attachment/108899/49a9e1ea-9495-3902-9e38-12c42e802171.gif[/img]
因此，当我们得知某个节点的索引为 i 时，可以通过以下“堆”的定义很容易地定位到它的子节点和父节点。

不仅如此，“堆”还有个特性：每个节点的键值一定总是大于（或小于）它的父节点。如果我们修改了某个节点的键值，这样就会破坏“堆”的这个特性，因此这时我们就要根据该节点的新键值与它的父节点和子节点的键值进行比较，对该节点进行“上移”或者“下移”操作，使之能够重新放置到合适位置。

这里我们了解一下“堆”的这两个很重要的操作：“上移”和“下移”。

这里我们假设这是一个“最大堆”，即“堆”的根节点保存的是键值最大的节点。即“堆”中每个节点的键值都总是大于它的子节点。

当某节点的键值大于它的父节点时，这时我们就要进行“上移”操作，即我们把该节点移动到它的父节点的位置，而让它的父节点到它的位置上，然后我们继续判断该节点，直到该节点不再大于它的父节点为止才停止“上移”。

现在我们再来了解一下“下移”操作。当我们把某节点的键值改小了之后，我们就要对其进行“下移”操作。首先，我们要取该节点的两个左右子节点中键值较大的一个，与该节点进行比较，如果该节点小于它的这个子节点，就把该节点移动到它的子节点的位置，而让它原来的子节点升到它的位置上。然后我们继续判断该节点，直到该节点不再小于它的左右子节点为止才停止“下移”。

现在我们再来看看如何把一个无序的序列建立成为一个“堆”？

根据“堆”的特性，我们可以从无序序列的最后一个节点的父节点开始，对其进行“下移”操作，直到序列的第一个节点为止。这样就可以保证每个节点都在合适的位置上，也就建立起了一个“堆”。

但是“堆”并不是一个完全排序的序列，因为“堆”只保证了父节点与子节点的位置关系，但并不保证左右子节点的位置关系。那么我们如何进行“堆排序”呢？

由于一个“堆”的根节点必然是整个序列中最大的元素，因此对于一个排序的序列而言，每个“堆”中我们只能得到一个有效的元素。如果我们拿掉根节点，再对剩下的序列重新排列组成一个“堆”，反复如此，我们就可以依次得到一个完整的排序序列了。

当然，为了简化操作，每次我们只需要把根节点与最后一个位置的节点交换，然后把最后一个位置排除之外，对根节点进行“下移”操作即可。

下面展示一段代码简单实现了堆排序，上面的文字转载自[url]http://jaskell.blogbus.com/logs/3272503.html[/url]，因为我觉得他说得比清楚了，我只是附上自己写的一段代码，这样看我代码会更容易理解了，希望能更加清晰理解堆排序：

package org.rjb.Heap;
/**
 * 通过不断建大顶堆进行排序
 * @author ljp
 *
 */
public class HeapTest {
	public static void main(String args[]){
		//待排序的数组
		int num[]={3,1,5,7,8,2,0,9};
		//创建堆，并排好序
		createHeap(num);
		for(int j=0;j<num.length;j++){
			System.out.print(num[j]+" ");
		}System.out.println();	
	}
	/**
	 * 创建大顶堆
	 * @param num
	 */
	public static void createHeap(int[] num){
		//从最后一个节点开始，对第i个节点，其父节点的位置为(int)Math.floor((i-1)/2)
		for(int i=num.length-1;i>0;i--){
			//如果当前节点比其父节点大的话就把当前节点上虑，既和父节点交换位置
			if(num[i]>num[(int)Math.floor((i-1)/2)]){
				siftUp(num,(int)Math.floor(i/2-1),i);			
			}
		}
	}
	/**
	 * 上虑操作
	 * @param num 待排序的数组
	 * @param h 下虑元素所处的层数
	 * @param key 当前节点在数组中的位置
	 */
	public static void siftUp(int[] num,int h,int key){
		//先交换父子节点的位置
		int temp=num[key];
		num[key]=num[(int)Math.floor((key-1)/2)];
		num[(int)Math.floor((key-1)/2)]=temp;
		//对交换之后的节点可能存在下虑，既如果比子节点的键值要小的话还要和子节点位置进行互换
		siftDown(num,h,key);
	}
	/**
	 * 下滤操作
	 * @param num
	 * @param h
	 * @param key
	 */
	public static void siftDown(int[] num,int h,int key){
		//lastLayer表示的是最后那层所在的层数
		int lastLayer=(int)Math.floor(num.length/2-1);
		//下虑操作最多下虑到最后一层
		while(h<lastLayer){
			//maxChild记录的是键值最大的子孩子
			int maxChild=0;
			//flag用来标识当前节点是否有子孩子
			boolean flag=false;
			//index用来表示子孩子中具有最大键值的那个所在数组中的位置
			int index=0;
			//当2*key+2<num.length时表示有两个子孩子
			if(2*key+2<num.length){
				//当有两个子孩子时就找出具有最大键值的子孩子
				if(num[2*key+2]>num[2*key+1]){
					maxChild=num[2*key+2];
					index=2*key+2;
				}else{
					maxChild=num[2*key+1];
					index=2*key+1;
				}
				flag=true;
			}else if(2*key+1<num.length){//当2*key+1<num.length时表示有一个子孩子
				maxChild=num[2*key+1];
				index=2*key+1;
				flag=true;
			}
			//如果有子孩子就判断最大子孩子的值比当前节点值的大小
			if(flag){
				if(maxChild>num[key]){
					int temp=num[key];
					num[key]=num[index];
					num[index]=temp;
					key=index;
				}else{
					break;
				}
			}
			//h++表示下移一层
			h++;
		}
	}
}

代码就只是一个简单的测试类了，只有几个方法实现上虑下虑操作，以前只是知道堆排序，从没有实现过，今天硬是鼓起勇气写了这个，还是能写出来的，所以如果有地方写得不怎么好的，希望各位多多指点。