堆排序分析及优化

堆排序,是利用堆结构进行排序,一般是利用最大堆,即根节点比左右两个子树的节点都大,具体算法步骤如下。

一、创建堆

        首先将数组中的元素调整成堆,对应下面程序中的createHeap(List<Integer> list)方法。创建堆就是从树中最后一个内节点(下标为(n-1)/2)开始调整数组中元素的位置,使以这个内节点为根的子树满足堆的结构。即依次将以(n-1)/2、(n-1)/2-1、(n-1)/2-2、...、1、0为根的子树调整为堆。

创建堆主要用了shiftDown操作,对应下面的shiftDown(List<Integer> list,int parent,int end)方法。该操作是不断将小元素下调的过程,如果根元素小于左右两个子树的较大者,那么根元素就要跟这个较大者进行交换,直到到达叶子节点为止。siftDown操作每下降一层要比较两次:1)选择左右子树的较大者,2)将较大者跟父亲比较。下降的最大高度即为父节点的高度。由结论:高度为h的满二叉树的所有节点的高度和为n-h-1,高度从0开始,叶子节点高度为0,此结论可由数学归纳法证明,可知最坏情况的比较次数约为2(n-h-1),即创建堆的复杂度度为O(n)

二、排序

当将数组调整成堆之后,由堆的定义可知,树的根就是最大的元素,这时我们可以将根删除,并将最后一个元素放到根的位置,然后将树重新调整为堆。重新调整为堆之后,根节点又为最大的元素,再删除,再调整,直到元素全部排序。(这里实际上是将最后一个元素和根元素交换,从此以后最后一个元素不在参与树的重新调整,即已经排好序的元素不再参与树的调整)。

shiftDown操作的时间复杂度为O(lgn),即树的高度,排序过程中一共进行了n-1的shiftDown操作,所以可以粗略的推断出堆排序的时间复杂度为O(nlgn)。空间复杂度为O(1)。

三、优化

堆中从根节点到叶节点的一条路径是有序的,最大堆是降序,我们在shiftDown操作时,实际上是在找根节点在某条路径上的一个插入位置,可以借鉴二分的思想,我们可以一次下降到当前高度h的一半的位置(在下降的过程中要将沿途的较大的子节点上移,这样在h/2高度形成空位),即h/2,再比较在一半高度h/2的节点与根节点的大小,如果比根节点大则继续寻找当前一半高度位置的元素即h/4,依次类推,如果当前高度的元素比根节点小,我们就引入shiftUp操作,即将根节点再上移,但由前面的分析可知,上移的次数是有限的,这样就将shiftDown的复杂度变为O(lglgn),堆排序的总体复杂度变为O(n*lglgn)

下面是堆排序的Java实现,未经优化,优化的代码以后有时间给出。

import java.util.Arrays;
import java.util.List;
/*
 *创建最大堆,并进行排序 
 */
public class HeapSort {
	
	public void swap(List<Integer> list, int m,int n){
		int temp = list.get(n);
		list.set(n, list.get(m));
		list.set(m,temp);
	}
	
	public List<Integer> createHeap(List<Integer> list){ //创建堆,从第一个非孩子结点开始调整,创建一个最大堆
		int n = list.size();
		for(int k = (n-1)/2;k >= 0;k--){
			shiftDown(list,k,n-1);
		}
		return list;
	}
	
	//将以parent为根节点的二叉树调整为堆
	public void shiftDown(List<Integer> list,int parent,int end){
		boolean flag = true;
		while(parent*2+1<=end && flag){ //如果存在左孩子就进行调整
			
			int lChild = parent*2+1;
			int max=0;
			if(lChild+1<=end){ //表示存在右孩子
				int rChild = lChild+1;
				max = list.get(lChild)>list.get(rChild)?lChild:rChild;
			}else{
				max = lChild;
			}
			if(list.get(max)>list.get(parent)){ //有子孩子比父亲大
				swap(list,max,parent);
				parent = max;
			}else{
				flag = false;//表示孩子都比父亲要小,不需要调整了
			}
		}
	}
	
	public void sort(List<Integer> heap){  //排序主过程
		int n = heap.size();
		int rmd = n-1;
		while(rmd>0){
			swap(heap,0,rmd);
			shiftDown(heap,0,rmd-1);
			rmd--;
		}
	}
	
	public static void main(String[] args) { //测试算法
		HeapSort hs = new HeapSort();
		List<Integer> list = null;
		list = Arrays.asList(3,0,23,6,5,43,23,566,8,5,34,23,667,34,123);
		hs.createHeap(list);
		hs.sort(list);
		for(int i=0;i<list.size();i++){
			System.out.print(list.get(i)+" ");
		}
	}
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。