堆排序java实现 博客分类： java数据结构&算法

/**
 * 大根堆，从小到大排序
 * 
 * @author Administrator
 * 
 */
public class HeapSorter {
	private static int N = 10000000;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			arr[i] = ((Double) (Math.random() * 1000)).intValue();
		}
		initHeap(arr, N);
		System.out.println("init check's result is " + checkInit(arr));
		doSort(arr);
		System.out.println("result check's result is " + checkResult(arr));
	}

	private static boolean checkInit(int[] arr) {
		boolean result = true;
		for (int i = 1; i <= N; i++) {
			result = result && isHeap(arr, i, N);
		}
		return result;
	}

	private static boolean checkResult(int[] arr) {
		boolean result = true;
		for (int i = 1; i <= N - 1; i++) {
			result = result && (arr[i] <= arr[i + 1]);
		}
		return result;
	}

	private static void doSort(int[] arr) {
		int maxIndex = N;
		while (maxIndex > 0) {
			arr[0] = arr[maxIndex];
			arr[maxIndex] = arr[1];
			arr[1] = arr[0];
			maxIndex--;
			buildHeap(arr, 1, maxIndex);
		}
	}

	private static void initHeap(int[] arr, int maxIndex) {
		for (int p = maxIndex / 2; p >= 1; p--) {
			buildHeap(arr, p, maxIndex);
		}
	}

	private static boolean isHeap(int[] arr, int i, int maxIndex) {
		boolean result = false;
		if (i > maxIndex / 2) {
			result = true;
		} else {
			if (arr[i] >= arr[2 * i]
					&& ((2 * i + 1 > maxIndex) || arr[i] >= arr[2 * i + 1])) {
				result = true;
			}
		}
		return result;
	}

	private static void buildHeap(int[] arr, int p, int maxIndex) {
		if (!isHeap(arr, p, maxIndex)) {
			int larger = p * 2;
			if (p * 2 + 1 <= maxIndex && arr[p * 2] < arr[p * 2 + 1]) {
				larger = p * 2 + 1;
			}
			arr[0] = arr[larger];
			arr[larger] = arr[p];
			arr[p] = arr[0];
			buildHeap(arr, larger, maxIndex);
		}
	}

}

 

堆排序的实现过程主要分2步，

第一步：初始化堆。

第二步：将堆的根（最大值）与最后一个元素交换，后针对剩余的无序的数列继续构造堆，以产生新的最大值

构造堆的过程：1.判断根是否满足堆的定义，如果不满足则交换，交换后判断发生交换后的新根是否满足根得定义，直到交换后的新根满足堆定义，则该子树堆构造完成。叶子节点都满足堆的定义

 

可以优化的地方：最后一个元素为堆里较小的值，将根与其交换后构造根得话比较与交换的次数较多。

 

 

 

 

 

“堆”定义

　　n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：

　　(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) //ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子

     若将此序列所存储的向量R[1..n]看做是一棵完全二叉树 的存储结构，则堆实质上是满足如下性质的完全二叉树： 　　树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

　【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。