/**
* 大根堆,从小到大排序
*
* @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),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
分享到:
相关推荐
堆排序 java实现
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
代码十分清楚的描述了堆排序是如何进行的,配合笔者写的博客,可以将此种算法掌握的十分牢靠,代码结构清晰。
数据结构与算法分析的一些有所帮助的课件,希望能帮到刚学习的人
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
堆排序算法Java实现
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
用Java实现的堆排序算法,二叉树转换为堆,然后排序
堆排序,和其他排序 java 实现 适合初学各种算法的童鞋
堆排序 堆排序.java 使用Java来实现
数据结构堆排序的java算法实现,里面用java语言实现了堆排序的算法实现,有输入和输出结果
Java实现堆排序.rar
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
堆排序 堆排序2.java 使用java源码来实现的 堆排序2.java 使用java源码来实现的 堆排序2.java 使用java源码来实现的 堆排序2.java 使用java源码来实现的
对于堆排序的java实现的理解,是初学数据结构的人的入门资源